Premium
Efficient algorithms for multiple destinations routeing
Author(s) -
Leung YiuWing,
Yum TakShing
Publication year - 1993
Publication title -
international journal of digital and analog communication systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.344
H-Index - 49
eISSN - 1099-1131
pISSN - 1047-9627
DOI - 10.1002/dac.4510060205
Subject(s) - heuristics , heuristic , computer science , computation , mathematical optimization , enhanced data rates for gsm evolution , integer programming , multicast , tree (set theory) , algorithm , consistent heuristic , mathematics , search algorithm , distributed computing , beam search , combinatorics , incremental heuristic search , artificial intelligence
A 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.