✦ LIBER ✦

Nonadaptive broadcasting in trees

✍ Scribed by Hovhannes A. Harutyunyan; Arthur L. Liestman; Kazuhisa Makino; Thomas C. Shermer

Publisher: John Wiley and Sons
Year: 2010
Tongue: English
Weight: 210 KB
Volume: 57
Category: Article
ISSN: 0028-3045
DOI: 10.1002/net.20396

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

k-Broadcasting in trees

✍ Hovhannes A. Harutyunyan; Arthur L. Liestman 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 147 KB

Optimal Broadcasting in Faulty Trees

✍ Petrişor Panaite; Andrzej Pelc 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 291 KB

We consider broadcasting a message from one node of a tree to all other nodes. In the presence of up to k link failures the tree becomes disconnected, and only nodes in the connected component C containing the source can be informed. The maximum ratio between the time used by a broadcasting scheme B

An Optimal Algorithm for Broadcasting Mu

An Optimal Algorithm for Broadcasting Multiple Messages in Trees

✍ Krzysztof Diks; Andrzej Lingas; Andrzej Pelc 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 118 KB

We consider multiple message broadcasting in tree networks. The source (considered as the root of the tree) has k messages which have to be broadcast to all nodes of the tree. In every time unit each node can send one of its already obtained messages to one of its children. A k-message broadcasting

Local broadcasting in a tree under minis

Local broadcasting in a tree under minisum criterion

✍ Jae-Moon Koh; Dong-Wan Tcha 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 501 KB

Low-cost minimum-time line-broadcasting

Low-cost minimum-time line-broadcasting schemes in complete binary trees

✍ A. Averbuch; I. Gaber; Y. Roditty 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 251 KB

Broadcasting in All-Output-Port Meshes o

Broadcasting in All-Output-Port Meshes of Trees with Distance-Insensitive Switching

✍ Petr Salinger; Pavel Tvrdı́k 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 648 KB

Meshes of trees are hybrids of meshes and trees with outstanding properties, namely small degree and diameter and large bisection width. Moreover, they are known to be area universal, i.e., they can simulate any network with the same wire area with only a polylogarithmic slowdown. Meshes of trees ar