Heuristic Algorithms for Broadcasting in Point-to-Point Computer Networks
- 1 September 1984
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-33 (9) , 804-811
- https://doi.org/10.1109/tc.1984.1676496
Abstract
We examine the problem of broadcasting in a point-to-point computer network where a message, originated by one node, is transmitted to all nodes, subject to the restriction that an informed node can call only one of its neighbors Auring a given time unit. A dynamic programming formulation for optimal broadcasting in general networks is given, and an exact algorithm based on it is developed. Since this algorithm is not very efficient for larger networks, we present a number of heuristics for achieving efficient near-optimal algorithms. In particular, we discuss in detail a class of heuristics which require finding at each step a least-weight maximum matching in a bipartite graph.Keywords
This publication has 12 references indexed in Scilit:
- Information Dissemination in TreesSIAM Journal on Computing, 1981
- Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problemsActa Informatica, 1981
- Minimum Broadcast TreesIEEE Transactions on Computers, 1981
- Minimum‐time line broadcast networksNetworks, 1980
- Minimal broadcast networksNetworks, 1979
- Query Processing in Distributed Database SystemIEEE Transactions on Software Engineering, 1979
- Minimum broadcast graphsDiscrete Mathematics, 1979
- A File Transfer Protocol (FTP)Computer Networks (1976), 1978
- Computer Communication Networks: Approaches, Objectives, and Performance ConsiderationsACM Computing Surveys, 1975
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite GraphsSIAM Journal on Computing, 1973