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 -