7
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Would you be looking for the graph center? If you have a tree, the center is always a single vertex or an edge. It can be found in linear time. $\endgroup$ – Juho Apr 10 '13 at 21:08
  • 3
    $\begingroup$ @Juho: note that the eccentricity at $v$ is the largest distance of any node from $v$. The OP is asking about the minimum distance to a leaf, which will often be different. So it's not clear that the graph center, dealing with vertices of minimal eccentricity, is the pertinent concept. $\endgroup$ – Niel de Beaudrap Apr 10 '13 at 21:27
  • $\begingroup$ @NieldeBeaudrap Yes, that's true. $\endgroup$ – Juho Apr 10 '13 at 21:27
5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

Perform breadth-first seach from all leaves in parallel, i.e. visit all neigbours of all leaves, then their respective neighbours, and so on. The node visited last is your winner.

If you let all searches share the visited flag, no vertex is visited twice. Since we have a tree, also every edge is visited only once. In total, we get linear runtime (in the number of nodes).

$\endgroup$
  • $\begingroup$ Oops, you beat me to it! $\endgroup$ – Niel de Beaudrap Apr 10 '13 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.