OJ Board

Hi,

I was hoping somebody could explain me an algorithm to find the 'central node' of a tree, i.e. - the node from which the maximum distance to any other vertex is minimized over all vertices.

Thank You

Identify the longest path of the tree. Then it's median node is the central node.

To identify the longest path, apply dfs from any node. Pick one of the deepest node from the dfs tree. Apply dfs again from this node. The path from this node to the deepest node of the second dfs tree is the longest path.

The first solution that comes to mind is to run Floyd-Warshall on the graph, then search for the optimal node. Almost as soon as I started typing that, I realized it sucked. So instead, I made up another algorithm and realized 20 minutes later it was broken. Sorry.

Floyd-Warshall takes O(n^3) time and O(n^2) space in the number of nodes when coded correctly.

Edit: Cho owns me

You can at the first step eliminate all the leaves of a tree, doing so decreases the largest distance by 1. We repeat this until one or two nodes remain, these will be the nodes with the largest distance to other nodes. You can use this algoritm to find the center of the tree in O(n).

Cosmin - Does your solution work on weighted trees?
Cho - I didn't really understand why the algo you suggested works.

Thanks

No my algorithm doesn't work on weighted trees. For weighted trees you could try something like this: add another node and join every leaf with this node and the weigth of each added edge will be 0. Now just apply the Dijkstra algorithm with heaps and the node that is farthest away from the new node will be the center. So the algoritm will be O(M log N) but the number of edges is O(M) so we have a O(N log N) solution.