### 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 language | English (US) |
---|---|

Title of host publication | Proceedings of the International Conference on Parallel Processing |

Editors | Robert M. Keller |

Publisher | IEEE |

Pages | 346-352 |

Number of pages | 7 |

ISBN (Print) | 081860560X |

State | Published - Dec 1 1984 |

### Publication series

Name | Proceedings 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

*Proceedings of the International Conference on Parallel Processing*(pp. 346-352). (Proceedings of the International Conference on Parallel Processing). IEEE.