Minimum k-broadcast graphs
| Autor: | E. Lazard, J.-C. König |
|---|---|
| Rok vydání: | 1994 |
| Předmět: |
Computer science
Applied Mathematics Symmetric graph Broadcasting 1-planar graph law.invention Combinatorics Modular decomposition Indifference graph Pathwidth Chordal graph law Line graph Discrete Mathematics and Combinatorics Networks Graphs Pancyclic graph MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Discrete Applied Mathematics. 53:199-209 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/0166-218x(94)90185-6 |
| Popis: | Broadcasting is an information dissemination process in which a message is to be sent from a single originator to all members of a network by placing calls over the communication lines of the network. We study here a variant of broadcasting called k-broadcast, where a processor can call several of its neighbours in one time unit. A k-broadcast graph is an n-vertex communication network that supports a broadcast from any one vertex to all other vertices in optimal time ⌈logk + 1 n⌉. A minimum k-broadcast graph is a k-broadcast graph having the minimum number of edges. In this paper, after giving simple results generalizing previously known results on 1-broadcasting, we find minimum k-broadcast graphs for k + 3 ⩽ n ⩽ 2k + 3. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|