1
$\begingroup$

Given an acyclic undirected graph alike to this one : enter image description here

(Here the center is the node '2', and the radius is 5)

What is the most efficient (ideally in O(n)) way to compute the radius of the tree ?

I've already used different methods like :

  • Computing the eccentricity of every node, and retrieving the minimal value (the naive way)
  • Repeatedly removing every leaf until there are only one or two nodes left (the centers of the graph)
  • Using BFS, getting the two farthest points, computing their path and getting the node in the middle

Is there a way to do this computation more efficiently ?

EDIT : Here I try to find the radius i.e. the vertices who minimizes the maximum distance to any vertex of the graph, not the diameter, which is not the same since the radius is not always the half of the diameter. I found almost nothing about this online

$\endgroup$
2
$\begingroup$

Yes, it can be done in $O(n)$ time.

Rooted trees

First let me describe how to do it for a rooted tree. We'll compute several quantities for each node $v$ in the tree:

  • Let $p(v)$ denote $v$'s parent.

  • Let $h(v)$ denote the height of $v$ (i.e., the distance from $v$ to its deepest descendant). You can compute $h(v)$ for all nodes $v$ in $O(n)$ time via a simple recursive traversal.

  • Let $f(v)$ denote the length of the longest simple path that starts $v \to p(v) \to w \to \cdots$ such that $w$ is a sibling of $v$, i.e., $p(v)=p(w)$ and $v \ne w$. In other words, it's the length of the longest path that starts from $v$ by going up once and then immediately going down. Note that

    $$f(v) = \max \{2+h(w) : p(w)=p(v), w \ne v\}.$$

    Suppose we've computed $h(v)$ for all nodes $v$. Also, suppose that for each node we keep track of its two children with the two largest $h(\cdot)$ values. Then, we can compute $f(v)$ for each node $v$ easily.

  • Let $g(v)$ denote the length of the longest simple path that starts $v \to p(v) \to \cdots$. In other words, it's the length of the longest path that starts by going up from $v$ (possibly several times). Note that $g(v) = \max \{ f(p^i(v))+i : i \ge 0\}$ and moreover

    $$g(v) = \max(f(v), g(p(v))+1).$$

    Therefore, if you've computed $f(v)$ for all nodes $v$, you can easily compute $g(v)$ for all nodes via a simple recursive traversal.

  • Let $e(v)$ denote the eccentricity of node $v$, i.e., $e(v) = \max\{d(v,w) : w \in V\}$. The eccentricity of a node $v$ is given by $e(v) = \max(h(v),g(v))$.

This gives us a way to label all the nodes with their eccentricity, in $O(n)$ time. Then we simply find the node whose eccentricity is the smallest. The algorithm runs in $O(n)$ time in all.

Unrooted trees

If we have an unrooted tree (as in the question), we can first turn it into a rooted tree (do a DFS; then the DFS tree will be a rooted version of the tree), then apply the previous algorithm.

$\endgroup$

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.