6

My problem is the following:

Given a tree (V, E), find the center node v such that sum{w in V}[dist(v,w)] is minimum, where dist(v,w) is the number of edges in shortest path from v to w. The algorithm should run in O(n) time (n being the number of nodes in a tree).

The questions here and here also ask for the center node but define it differently.

I haven't rigorously gone through the steps but I actually think that the solution to my problem should be similar to the solution of this problem.

However, I decided that I should share my problem with the community as it took me a while to navigate to the link, which however does not answer the question directly.

5
  • @maraca - I think what you're saying might be slightly incorrect. Think of a case where the resulting trees' height is one more from the tree you get due to one branch being one longer, but the total sum of distances is shorter. I'm not entirely sure this counter example could actually exist, I'm merely suggesting this should be examined... Commented Nov 23, 2016 at 15:07
  • @maraca Yes, I want to find an optimal root. I have though about it and I can give you a counter-example where solutions are not the same. Imagine a tree where the root has many neighbors, say m, each of which is a leave, and a single 'tail' of length say 3 (consisting of 3 vertices). Then the root vertex discovered by lowest depth would not be the one with many neighbors (it would be the first vertex on the tail, giving the result of min dist 2 to every other vertex), and the solution to my problem would be the one with many neighbors.
    – MindaugasK
    Commented Nov 23, 2016 at 15:08
  • @MindaugasK sorry my mistake, you want to minimize the distance of the sums to the root and not between all nodes...
    – maraca
    Commented Nov 23, 2016 at 15:17
  • 1
    @maraca Let's calculate the score for my example. Label the vertex with many leaves v and the first vertex of the tail looking from v with letter w. Then the score for v would be m*1 + 1 (to w) + 2 (element after w) + 3 (last tail element). While for w this sum would be 2*m (for leaves) + 1 (for v) + 1 (element after w) + 2 (last tail element). We get m + 6 vs 2*m + 4, and m + 6 < 2*m + 4 for m > 4
    – MindaugasK
    Commented Nov 23, 2016 at 15:18
  • @maraca exactly :)
    – MindaugasK
    Commented Nov 23, 2016 at 15:19

2 Answers 2

3

I came up with this solution:

1) Choose an arbitrary node as a root r, form a tree. For each subtree in this tree, calculate number of nodes in a subtree (the leaves are single-node-trees).

As an example for this tree

          1
        / | \
       2  3  4 
      / \     \
     5   6     7
        / \
       8   9      

the result would be

          9
        / | \
       5  1  2 
      / \     \
     1   3     1
        / \
       1   1    

2) Calculate the sum of distances for this chosen root. For the example, if you choose vertex 1 as a root, the sum of distances is 0 + 1 + 1 + 1 + 2 + 2 + 2 + 3 + 3 = 15

3) Traverse the tree in a depth-first-search manner. For example, starting from vertex 1, we traverse to vertex 4. We observe that for 7 nodes (1,2,3,5,6,8,9), we are getting further by 1 (add 7=9-2 to the score), for other 2 (4,7), we are getting closer by 1 (subtract 2). This gives the sum-of-distances equal to 15+(9-2)-2 = 20.

Suppose we traverse from 4 to 7 next. Now we get the sum of distances equal to 20+(9-1)-1 = 27 (getting further from 8 vertices, and getting closer to 1 vertex).

As another example if we traverse from 1 to 2, we get a sum of distances equal to 15+(9-5)-5 = 14. Vertex 2 is actually the solution for this example.

This would be my algorithm.

0

Each edge e={a,b} has the following properties:

  • a_count = number of nodes to a side (including a)
  • b_count = number of nodes to b side (including b)
  • a_sum = sum of distances from a to its subtree nodes
  • b_sum = sum of distances from b to its subtree nodes

a_count for node e={a,b} can be evaluated as following: * get all edges of a, not including e, sum their a_count * add 1 to the sum

a_sum for node e={a,b} can be evaluated as following: * get all edges of a, not including e, sum their a_sum * add a_count (it includes +1 for each enumerated edge and +1 for a)

You can freely do calculation in recursive function accepting node and direction parameters, saving obtained results in global array.

If you run this function on every edge of tree in both directions, you get full calculation for edges. Total time for all calculations is O(n), since once you get to some subtree, recursive nature will close the whole subtree in this direction and next calls will obtain result from global array, and you only do 2*n calls for your function.

For a node A final measure is sum of all B_count+B_sum of all edges connected to node. Do one run of this evaluation on nodes and select node with minimal value.

1
  • a_count and a_sum are clear, agree that you can do this in O(n) time for single edge, but how do you do this in O(n) for all edges?
    – MindaugasK
    Commented Nov 23, 2016 at 18:21

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.