Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by A. Srinivasan

38th Annual Symposium on Foundations of Computer Science (FOCS '97)

Miami Beach, FL

October 19-October 22

ISBN: 0-8186-8197-7

	ASCII Text	x
	A. Srinivasan, "Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems," Foundations of Computer Science, Annual IEEE Symposium on, pp. 416, 38th Annual Symposium on Foundations of Computer Science (FOCS '97), 1997.

	BibTex	x
	@article{ 10.1109/SFCS.1997.646130, author = {A. Srinivasan}, title = {Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems}, journal ={Foundations of Computer Science, Annual IEEE Symposium on}, volume = {0}, year = {1997}, issn = {0272-5428}, pages = {416}, doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.1997.646130}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Foundations of Computer Science, Annual IEEE Symposium on TI - Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems SN - 0272-5428 SP EP A1 - A. Srinivasan, PY - 1997 KW - multiprocessor interconnection networks; edge-disjoint paths; unsplittable flow; routing problems; multi-commodity flow relaxation VL - 0 JA - Foundations of Computer Science, Annual IEEE Symposium on ER -

A. Srinivasan, Dept. of Inf. Syst. & Comput. Sci., Nat. Univ. of Singapore, Singapore

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.1997.646130

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.

Index Terms:

multiprocessor interconnection networks; edge-disjoint paths; unsplittable flow; routing problems; multi-commodity flow relaxation

Citation:

A. Srinivasan, "Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems," focs, pp.416, 38th Annual Symposium on Foundations of Computer Science (FOCS '97), 1997

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.