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
Volume Number6
Issue Number2
PublisherJohn Wiley & Sons Inc.
Place of PublicationUnited States
Pages87 - 95
LanguagesEnglish-United Kingdom
KeywordsMultiple destinations, Routeing algorithms

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