Nonadaptive broadcasting in trees
| Autor: | Thomas C. Shermer, Arthur L. Liestman, Kazuhisa Makino, Hovhannes A. Harutyunyan |
|---|---|
| Rok vydání: | 2010 |
| Předmět: |
021103 operations research
Computer Networks and Communications business.industry Minimum time 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology Computer Science::Computational Complexity Broadcasting 01 natural sciences Vertex (geometry) Combinatorics 010201 computation theory & mathematics Hardware and Architecture business Time complexity Broadcast time Software Computer Science::Information Theory Information Systems Mathematics |
| Zdroj: | Networks. 57:157-168 |
| ISSN: | 0028-3045 |
| DOI: | 10.1002/net.20396 |
| Popis: | 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. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(2), 157–168 2011 © 2011 Wiley Periodicals, Inc. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text