Title :
Approximation algorithms for multiconstrained quality-of-service routing
Author :
Song, Meongchul ; Sahni, Sartaj
Author_Institution :
Samsung Electron. Co., Gyeonggi, South Korea
fDate :
5/1/2006 12:00:00 AM
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;
Journal_Title :
Computers, IEEE Transactions on
