[Math] Rooted Tree and Greedy Algorithms

algorithmscomputer sciencegraph theorytrees

In a Rooted Tree, we have a message on Root. in each step, each node that has a one copy of message, can transfer this message to at most one of it's childeren. we want to use minimum step and send the message to all nodes. for each node v, d(v) and c(v) shows the distance v to it's deepest leaf and number of it's childs. i propose two greedy algorithm, but i couldent find any prove or counterexample.

1) each node that recive a message, in each step send a message to one of childeren taht has a maximum d(v).

2) each node that recive a message, in each step send a message to one of childeren taht has a maximum c(v).

anyone could help me?

Best Answer

Both the greedy algorithms are wrong. Possible counterexamples are:

  1. A tree in which the maximum depth $max[d(v_i)]$ is smaller than maximum no. of children $max[d(c_i)]$.
  2. A tree in which the maximum depth $max[d(v_i)]$ is greater than maximum no. of children $max[d(c_i)]$.

A possible algorithm that comes to mind is the following: Start with the lowest level. Since these are leaves, give them a score of $s_i = d(v_i)$. In fact all leaves get this score. Now move a level up and give a score of $s_i = c_i + max\{s_{j_1},s_{j_2},\ldots ,s_{j_{c_i}}\}$. After you given scores to all vertices, the min. time it takes to transmit message to all is the score of the root.

Related Question