(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