[Solved]: Given a tree, find a vertex which maximizes the minimum distance to any leaf

Problem Detail: 

If I am given a graph which forms a tree, I am interested in finding a vertex which maximizes the minimum distance to any leaf.

I am sure this problem has been studied before. Does anybody know the name of this problem or an algorithm for solving it?

Asked By : Tex

Answered By : Niel de Beaudrap

To find a vertex of maximum distance from any leaf, you can perform a breadth-first search starting from many starting points, i.e. the leaves. Because a BFS visits each node by the shortest possible path from the source(s) of the search, we can easily attribute to each node the distance to the nearest leaf.

• Insert into a queue a collection of pairs $(\ell,0)$ for $\ell$ ranging over all leaves, and record $\textrm{max} = 0$.

• Repeat the following until the queue is empty:

  1. Pop a pair $(v,d)$ off the queue. If $d = \textrm{max}$, insert $v$ in a collection of maximum-distance elements.

  2. If there are nodes adjacent to $v$ which haven't been visited, push a pair $(w,d+1)$ into the queue for each such neighbour $w$, marking them as having been visited. If there are any such $w$ at all, empty the collection of maximum-distance elements (if it is non-empty), and set $\textrm{max} = d+1$.

The result is a collection of nodes which are all at distance at least $\textrm{max}$ from any leaf.

Let $n = |V|$ (note that $m = |E| = n-1$). Assuming that we can populate the queue with the leaves of the tree in time $O(n)$ by examining all nodes of the graph, and that the vertices have adjacency lists of their neighbours, we "traverse" each edge twice to consider the neighbours of each vertex; then this algorithm takes $O(n+m) = O(n)$ time. It also works for non-trees, taking again $O(n+m)$ time.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11208