Efficient algorithms for multiple destinations routing

Yiu Wing LEUNG*, Tak Shing Yum

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference contributionpeer-review

2 Citations (Scopus)

Abstract

The multiple-destination routing (MDR) problem is formulated as a zero-one integer programming problem, and a technique for reducing the computation required for optimum solution is proposed. Three heuristics are designed for connecting a large number of nodes in the network. Heuristic A can offer different degrees of optimality with different amounts of time allowed for the solution of the MDR problem. Heuristic B is a modification of Prim's algorithm for minimum spanning trees. It gives a fairly good solution with very little computation. Heuristic C is for minimizing the number of edges in the multicast tree. The MDR problem is identical to this problem when all link costs are the same. It always gives a better solution than Heuristic B. Simulation on two example networks shows that all three heuristics give better solutions (or lower-cost connection paths) than the improved RS algorithm.

Original languageEnglish
Title of host publicationConference Record - International Conference on Communications
PublisherPubl by IEEE
Pages1311-1317
Number of pages7
ISBN (Print)0780300068
Publication statusPublished - 1991
EventInternational Conference on Communications - ICC 91 - Denver, CO, USA
Duration: 23 Jun 199126 Jun 1991

Publication series

NameConference Record - International Conference on Communications
Volume3
ISSN (Print)0536-1486

Conference

ConferenceInternational Conference on Communications - ICC 91
CityDenver, CO, USA
Period23/06/9126/06/91

Scopus Subject Areas

  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Efficient algorithms for multiple destinations routing'. Together they form a unique fingerprint.

Cite this