0
$\begingroup$

"Given a graph G, the remoteness of a vertex v is the distance from v to the vertex u that is farthest from v in G. That is, the shortest path from v to u is as long as possible. A vertex of G with the smallest remoteness is called a middle vertex of G" Find the middle on O(n+m) where n,m are the number of vertices and edges respectively

I have this one idea and was wondering if it is valid: Start with the tree, remove all leaves on the tree. Repeat this until we have either one vertex left or we have to vertices joined by an edge. These vertices will have the shortest longest path. As these 2/1 vertices will be on the longest path/diameter of the graph and be in the middle of it. So these are middle vertices. I have applied this to some example trees and got the correct answer. Is it valid? Thanks

$\endgroup$
3
  • $\begingroup$ You talk about graphs and trees. Which is it? $\endgroup$
    – Nathaniel
    Commented May 8 at 11:48
  • $\begingroup$ Also the algorithm that you describe does not seem to be in $\mathcal{O}(n + m)$. $\endgroup$
    – Nathaniel
    Commented May 8 at 11:49
  • $\begingroup$ @Nathaniel oh does it not? My professor shared a solution to a different question using the same process and stated the run time is that. And it's about trees $\endgroup$ Commented May 8 at 12:00

1 Answer 1

0
$\begingroup$

You can find the diameter of the tree, and pick the middle vertex (or one of its two middle vertices). A simpler linear time algorithm to find a diameter would be:

  • rooting the tree arbitrarily
  • find a maximum depth leaf $u$
  • find the leaf $v$ farthest from $u$ (either by rooting the tree in $u$ or using BFS).

The algorithm you describe is also correct, because a middle vertex of the tree is also a vertex $v$ such that the tree rooted in $v$ has minimal height $h$. Removing leaves means reducing the height by one (and the root is necessarily removed last, because the tree has two children of height $h-1$ and $h-1-\varepsilon$, with $\varepsilon\in \{0,1\}$, otherwise using another root would reduce its height).

It can indeed be run in linear time, but not using naive data structures.

$\endgroup$
1
  • $\begingroup$ Cool thanks for the help! $\endgroup$ Commented May 8 at 12:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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