Efficient algorithms for multiple destinations routeing
Publication in refereed journal


Times Cited
Altmetrics Information
.

Other information
AbstractA number of important problems in computers and telecommunications, such as distributed databases and multipoint multimedia conferencing, all require the solution of a generic problem called multiple destinations routeing (MDR). In this paper, we formulate the MDR problem as a zero‐one integer programming problem and propose a technique to reduce the computation required for the optimum solution. Three heuristics are designed for large MDR problems. Heuristic A can offer different degrees of optimality with different amounts of time allowed for the solution. Heuristic B is a modification of Prim's algorithm for the minimum spanning tree. It gives a fairly good solution with very little computation. Heuristic C is based on Heuristic B and is for minimizing the number of edges in the multicast tree (i.e. assuming that all edge weights are the same). It always gives a better solution than Heuristic B. Simulation on two example networks shows that Heuristics A and C always give better solutions (or lower cost connection paths) than the improved RS algorithm, which has up to now been the best heuristic. Copyright © 1993 John Wiley & Sons, Ltd.
All Author(s) ListLeung Y.-W., Yum T.-S.
Journal nameInternational Journal of Communication Systems
Year1993
Month1
Day1
Volume Number6
Issue Number2
PublisherJohn Wiley & Sons Inc.
Place of PublicationUnited States
Pages87 - 95
ISSN1074-5351
LanguagesEnglish-United Kingdom
KeywordsMultiple destinations, Routeing algorithms

Last updated on 2020-21-05 at 23:45