Minimum broadcast tree decompositions |
| |
Authors: | Matthew Walsh |
| |
Institution: | Department of Mathematical Sciences, Indiana-Purdue University Fort Wayne, Fort Wayne IN, 46805-1499, USA |
| |
Abstract: | Recursive constructions for decomposing the complete directed graph Dn into minimum broadcast trees of order n are given, thereby showing the existence of such decompositions for all n. Such decompositions can be used for a routing system in a network where every participant has the ability to broadcast a message to the group; as each arc is used in only one tree, a participant’s further actions upon receipt of a message depend only on its sender, and so all routing information can be stored locally rather than in the message itself. |
| |
Keywords: | Minimum broadcast tree Graph decomposition |
本文献已被 ScienceDirect 等数据库收录! |
|