In a graph tree, is there any smart/existing/efficient algorithm to find linear segments of defined length?For example given a tree graph:g = {1 -> 2, 2 -> 4, 3 -> 6, 4 -> 8, 6 -> 12, 1 -> 3, 2 -> 5, 3 -> 7,    4 -> 9};TreePlot[g, VertexLabeling -> True] How can one find all linear segments of length 4. In this example this would be 1 2 4 81 2 4 91 3 6 122 1 3 72 1 3 69 4 2 5...This is probably a common problem, but I guess I have not yet found the right keywords for google. The naive implementation would be to visit every node, then recursively try to get four nodes away and delete all duplicated segments at the end...
Finding paths of certain length in trees
algorithms;graphs;trees;enumeration