Efficient algorithms for multiple destinations routing

Yiu Wing Leung; Tak Shing Yum

doi:10.1109/ICC.1991.162224

Efficient algorithms for multiple destinations routing

Yiu Wing Leung^*, Tak Shing Yum

^*Corresponding author for this work

Department of Computer Science

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-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 language	English
Title of host publication	IEEE International Conference on Communications, ICC 1991
Publisher	IEEE
Pages	1311-1317
Number of pages	7
ISBN (Print)	0780300068, 9780780300064
DOIs	https://doi.org/10.1109/ICC.1991.162224
Publication status	Published - 23 Jun 1991
Event	International Conference on Communications - ICC 1991 - Denver, CO, USA Duration: 23 Jun 1991 → 26 Jun 1991

Publication series

Name	IEEE International Conference on Communications
ISSN (Print)	0536-1486

Conference

Conference	International Conference on Communications - ICC 1991
City	Denver, CO, USA
Period	23/06/91 → 26/06/91

Scopus Subject Areas

Computer Networks and Communications
Electrical and Electronic Engineering

Access to Document

10.1109/ICC.1991.162224

Cite this

@inproceedings{0885a350075f49c28056fefb05de4ea8,

title = "Efficient algorithms for multiple destinations routing",

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.",

author = "Leung, {Yiu Wing} and Yum, {Tak Shing}",

year = "1991",

month = jun,

day = "23",

doi = "10.1109/ICC.1991.162224",

language = "English",

isbn = "0780300068",

series = "IEEE International Conference on Communications",

publisher = "IEEE",

pages = "1311--1317",

booktitle = "IEEE International Conference on Communications, ICC 1991",

address = "United States",

}

TY - GEN

T1 - Efficient algorithms for multiple destinations routing

AU - Leung, Yiu Wing

AU - Yum, Tak Shing

PY - 1991/6/23

Y1 - 1991/6/23

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0026405873&partnerID=8YFLogxK

U2 - 10.1109/ICC.1991.162224

DO - 10.1109/ICC.1991.162224

M3 - Conference proceeding

AN - SCOPUS:0026405873

SN - 0780300068

SN - 9780780300064

T3 - IEEE International Conference on Communications

SP - 1311

EP - 1317

BT - IEEE International Conference on Communications, ICC 1991

PB - IEEE

T2 - International Conference on Communications - ICC 1991

Y2 - 23 June 1991 through 26 June 1991

ER -

Efficient algorithms for multiple destinations routing

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this