Title :
Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems
Author :
Srinivasan, Aravind
Author_Institution :
Dept. of Inf. Syst. & Comput. Sci., Nat. Univ. of Singapore, Singapore
Abstract :
We present improved approximation algorithms for a family of problems involving edge-disjoint paths and unsplittable flow, and for some related routing problems. The central theme of all our algorithms is the underlying multi-commodity flow relaxation
Keywords :
computational complexity; graph theory; multiprocessor interconnection networks; network routing; edge-disjoint paths; multi-commodity flow relaxation; routing problems; unsplittable flow; Approximation algorithms; Bandwidth; Channel allocation; Computer science; High speed integrated circuits; IEL; Image motion analysis; Information systems; Optical fiber networks; Routing;
Conference_Titel :
Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium on
Conference_Location :
Miami Beach, FL
Print_ISBN :
0-8186-8197-7
DOI :
10.1109/SFCS.1997.646130
