Minimum Broadcast Trees
- 1 May 1981
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-30 (5) , 363-366
- https://doi.org/10.1109/tc.1981.1675796
Abstract
"Broadcasting" is an information dissemination process in which a member of a system generates a message communicated to all other members. We model this process by ordered rooted trees and investigate a special class of rooted trees allowing broadcasting from the root to all other vertices of the tree in the minimum time (over all rooted trees with n vertices). We characterize trees from this class ("mbt") and give an algorithm deciding membership in the class. We also present an algorithm to construct all mbt's with a given number of vertices and give a recursive formula to count these trees.Keywords
This publication has 10 references indexed in Scilit:
- Information Dissemination in TreesSIAM Journal on Computing, 1981
- Minimum Broadcast TreesIEEE Transactions on Computers, 1981
- Minimal broadcast networksNetworks, 1979
- Minimum broadcast graphsDiscrete Mathematics, 1979
- Reverse path forwarding of broadcast packetsCommunications of the ACM, 1978
- A data structure for manipulating priority queuesCommunications of the ACM, 1978
- Some Complexity Results for Matrix Computations on Parallel ProcessorsJournal of the ACM, 1978
- New gossips and telephonesDiscrete Mathematics, 1975
- A Cure for the Telephone DiseaseCanadian Mathematical Bulletin, 1972
- Gossips and telephonesDiscrete Mathematics, 1972