TY - GEN

T1 - BROADCASTING IN POINT-TO-POINT COMPUTER NETWORKS.

AU - Scheuermann, Peter

AU - Wu, Geoffrey

PY - 1984/12/1

Y1 - 1984/12/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=0021560915&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0021560915&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0021560915

SN - 081860560X

T3 - Proceedings of the International Conference on Parallel Processing

SP - 346

EP - 352

BT - Proceedings of the International Conference on Parallel Processing

A2 - Keller, Robert M.

PB - IEEE

ER -