DocumentCode
888213
Title
Approximation algorithms for multiconstrained quality-of-service routing
Author
Song, Meongchul ; Sahni, Sartaj
Author_Institution
Samsung Electron. Co., Gyeonggi, South Korea
Volume
55
Issue
5
fYear
2006
fDate
5/1/2006 12:00:00 AM
Firstpage
603
Lastpage
617
Abstract
We propose six new heuristics to find a source-to-destination path that satisfies two or more additive constraints on edge weights. Five of these heuristics become ε-approximation algorithms when their parameters are appropriately set. The performance of our new heuristics is compared experimentally with that of two recently proposed heuristics for the same problem.
Keywords
graph theory; quality of service; telecommunication network routing; approximation algorithm; graph theory; multiconstrained quality-of-service routing; source-to-destination path; Approximation algorithms; Bandwidth; Costs; Delay; Heuristic algorithms; Jitter; Partitioning algorithms; Quality of service; Routing; Terminology; Quality of service routing; approximation algorithm; heuristic.; interval partitioning;
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
ISSN
0018-9340
Type
jour
DOI
10.1109/TC.2006.67
Filename
1613840
Link To Document