Nonadaptive Broadcasting in Trees

作者：Harutyunyan Hovhannes A; Liestman Arthur L^*; Makino Kazuhisa; Shermer Thomas C

来源：Networks, 2011, 57(2): 157-168.

DOI：10.1002/net.20396

• broadcasting
• path
• tree
• universal list
• nonadaptive

We study nonadaptive broadcasting in trees, a process of sending a message from one vertex in a tree to all other vertices. In the nonadaptive model, each vertex has a specified, ordered list of its neighbors. After receiving a broadcast message, a vertex sends the message to its neighbors, one after another, in the order specified by the list. The broadcast is completed when all vertices have received the message. We obtain lower and upper bounds on the minimum time required to complete a nonadaptive broadcast in a tree and improved upper bounds for general graphs. We give a polynomial time algorithm for determining the minimum nonadaptive broadcast time of any given tree. We also show how to construct the largest possible trees having a given nonadaptive broadcast time.

• 出版日期2011-3