patternMinor
Shortest path visiting all nodes in an unrooted tree
Viewed 0 times
nodespathunrootedshortestallvisitingtree
Problem
I have a tree. This tree has no particular root (free-tree).
I want to find a path that visit all nodes. This path has to be the shortest possible.
All edges are considered to have a distance of 1.
My problem is not finding a Hamiltonian path, because I don't have any restriction on the number of times a node can be visited.
We don't know the source node of the path. The source has to be one allowing us to find the shortest path visiting all nodes.
I want to find a path that visit all nodes. This path has to be the shortest possible.
All edges are considered to have a distance of 1.
My problem is not finding a Hamiltonian path, because I don't have any restriction on the number of times a node can be visited.
We don't know the source node of the path. The source has to be one allowing us to find the shortest path visiting all nodes.
Solution
Hint: Start from a source $s \in V$ to visit all vertices that $V$ is the set of vertices of the tree. All edges are visited twice except those which contribute to the longest path.
Then, the shortest possible path, visiting all nodes, is equal to $2 \times |E| - |P_{L}|$, where $|E|$ denotes the number of edges, and $|P_{L}|$ is the number of edges in the longest path. This can be achieved with time complexity $O (E)$.
Then, the shortest possible path, visiting all nodes, is equal to $2 \times |E| - |P_{L}|$, where $|E|$ denotes the number of edges, and $|P_{L}|$ is the number of edges in the longest path. This can be achieved with time complexity $O (E)$.
Context
StackExchange Computer Science Q#48473, answer score: 2
Revisions (0)
No revisions yet.