BROADCASTING IN POINT-TO-POINT COMPUTER NETWORKS.

Peter Scheuermann*, Geoffrey Wu

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

The authors 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 during 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, a number of heuristics for achieving efficient, near-optimal algorithms are presented. In particular, a class of heuristics that require finding at each step a least-weight maximum matching in a bipartite graph is discussed in detail.

Original languageEnglish (US)
Title of host publicationProceedings of the International Conference on Parallel Processing
EditorsRobert M. Keller
PublisherIEEE
Pages346-352
Number of pages7
ISBN (Print)081860560X
StatePublished - Dec 1 1984

Publication series

NameProceedings of the International Conference on Parallel Processing

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'BROADCASTING IN POINT-TO-POINT COMPUTER NETWORKS.'. Together they form a unique fingerprint.

  • Cite this

    Scheuermann, P., & Wu, G. (1984). BROADCASTING IN POINT-TO-POINT COMPUTER NETWORKS. In R. M. Keller (Ed.), Proceedings of the International Conference on Parallel Processing (pp. 346-352). (Proceedings of the International Conference on Parallel Processing). IEEE.