Heuristic Algorithms for Broadcasting in Point-to-Point Computer Networks

Peter Scheuermann, Geoffrey Wu

Research output: Contribution to journalArticlepeer-review

45 Scopus citations

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 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, 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.

Original languageEnglish (US)
Pages (from-to)804-811
Number of pages8
JournalIEEE Transactions on Computers
VolumeC-33
Issue number9
DOIs
StatePublished - Sep 1984

Keywords

  • Bipartite graph
  • dynamic programming
  • heuristic algorithms
  • least-weight maximum matching
  • minimum-delay broadcasting
  • point-to-point computer networks

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Heuristic Algorithms for Broadcasting in Point-to-Point Computer Networks'. Together they form a unique fingerprint.

Cite this