TY - GEN
T1 - Provably good approximation to minimum cost delay-constrained multicast trees
AU - Xue, Guoliang
N1 - Publisher Copyright:
© 1999 IEEE.
PY - 1999
Y1 - 1999
N2 - Multicast is an important operation in communication systems. In many real-time system applications, we are interested in finding a low-cost multicast tree satisfying a set of delay-constraints. Finding a minimum cost multicast tree is NP-hard, even in the case where the cost and delay of an edge are identical. In this paper, we present an efficient approximation algorithm for computing a low-cost multicast tree satisfying delay-constraints. Unlike most algorithms proposed in the literature, our algorithm has a provably good performance bound when the cost and delay of an edge are identical. This is achieved using a trade-off between a Steiner minimum tree and a shortest path tree. We also discuss extensions to communication systems where the cost and delay of an edge are different.
AB - Multicast is an important operation in communication systems. In many real-time system applications, we are interested in finding a low-cost multicast tree satisfying a set of delay-constraints. Finding a minimum cost multicast tree is NP-hard, even in the case where the cost and delay of an edge are identical. In this paper, we present an efficient approximation algorithm for computing a low-cost multicast tree satisfying delay-constraints. Unlike most algorithms proposed in the literature, our algorithm has a provably good performance bound when the cost and delay of an edge are identical. This is achieved using a trade-off between a Steiner minimum tree and a shortest path tree. We also discuss extensions to communication systems where the cost and delay of an edge are different.
KW - Approximation algorithms
KW - communication systems
KW - minimum cost delay-constrained multicast trees
UR - http://www.scopus.com/inward/record.url?scp=84940693780&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84940693780&partnerID=8YFLogxK
U2 - 10.1109/ICCCN.1999.805581
DO - 10.1109/ICCCN.1999.805581
M3 - Conference contribution
AN - SCOPUS:84940693780
SN - 0780357949
SN - 9780780357945
T3 - Proceedings - 8th International Conference on Computer Communications and Networks, ICCCN 1999
SP - 610
EP - 614
BT - Proceedings - 8th International Conference on Computer Communications and Networks, ICCCN 1999
A2 - Somani, Arun
A2 - Park, EK
A2 - Dixit, Sudhir
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 8th International Conference on Computer Communications and Networks, ICCCN 1999
Y2 - 11 October 1999 through 13 October 1999
ER -