I am looking for an algorithm with time complexity in $\mathcal O(|V|)$ that determines whether a given graph $G=(V,E)$ is a caterpillar tree.
A caterpillar tree is a tree that has a path to which all nodes are connected by a maximum of one edge. So for every vertex v there is a vertex u on the path so that the disctance between v und u is at most 1. In other words, removing all the leaves results in a simple path.
The only progress I've made so far is that I could use breadth-first search or depth-first search to traverse the graph. They have a complexity of $\mathcal O(|V|+|E|)$, but in a caterpillar tree, $|E|=|V|-1$, so I end up in $\mathcal O(2|V|)$ = $\mathcal O(|V|)$.
Is that idea correct? If so, then how can I modify BFS/DFS to do what I want? I am thinking of adding a branch depth counter of some sort and allowing only one branch with length >1 (the central path of the caterpillar), but I have no idea how to implement that without changing the original algorithm too much.
Asked By : Jorge
Answered By : Juho
When considering such recognition algorithms, it is sometimes helpful to consider equivalent characterizations of the graph in question. Your observations and ideas are valid.
In other words, we can first prove that caterpillars are such trees that when you delete all the leaves and incident edges, you are left with a path graph. This immediately suggest a simple linear time algorithm: check that your input graph is a tree, remove all the leaves, and check that you have a path.
In fact, I suggest you divide your problem into 3 subtasks you can work on independently:
- Implement a function that outputs YES/NO based on whether the input graph is a tree.
- Implement a function that removes all the leaves and the edges incident to them from the input graph.
- Implement a function that outputs YES/NO based on whether the input graph is a path.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/30623
0 comments:
Post a Comment
Let us know your responses and feedback