Peter Scheuermann*, Geoffrey Wu

*Corresponding author for this work

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

1 Scopus citations


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
Number of pages7
ISBN (Print)081860560X
StatePublished - 1984

Publication series

NameProceedings of the International Conference on Parallel Processing

ASJC Scopus subject areas

  • General Engineering


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

Cite this