Decision algorithms for unsplittable flow and the half-disjoint paths problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Decision algorithms for unsplittable flow and the half-disjoint paths problem

Full text

Pdf (1.28 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 530 - 539

Year of Publication: 1998

ISBN:0-89791-962-9

Author

Jon M. Kleinberg

Department of Computer Science, Cornell University, Ithaca, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 17, Citation Count: 9

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/276698.276867 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Stefan Arnborg , Andrzej Proskurowski, Linear time algorithms for NP-hard problems restricted to partial k-trees, Discrete Applied Mathematics, v.23 n.1, p.11-24, April 1989 [doi>10.1016/0166-218X(89)90031-0]
	2	B, Bollobfis, A. Thomason, "Highly linked graphs," Combinaiorica 16(1996), pp. 313-320.
	3	A, Frank, "Packing paths, cuts, and circuits- a survey," in Paths, Flows, and VLSi-Layout, B. Korte, L, Loves, H.J. PrSmel, A. Schrijver, Eds., Berlin: Springer-Verlag, 1990, pp. 49-100.
	4	Naveen Garg , Vijay V. Vazirani , Mihalis Yannakakis, Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees, with Applications to Matching and Set Cover, Proceedings of the 20th International Colloquium on Automata, Languages and Programming, p.64-75, July 05-09, 1993
	5	It.M, Karp, "On the computational complexity of combinatorial problems, Networks 5(1975), pp. 45- 68.
	6	J. M. Kleinberg, Single-source unsplittable flow, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.68, October 14-16, 1996
	7	J. Kzeinberg , E. Tardos, Disjoint paths in densely embedded graphs, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.52, October 23-25, 1995
	8	Stavros G. Kolliopoulos , Clifford Stein, Improved Approximation Algorithms for Unsplittable Flow Problems, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.426, October 19-22, 1997
	9	M. Middendorf, F. Pfeiffer, "On the complexity of the disjoint paths problem," Combinatorica, ls(1993), pp. 97-107.
	10	N. Robertson, P.D. Seymour, "An outline of a disjoint paths algorithm," in Paths, Flows, and V~SI- Layout, B. Korte, L. Lov~z, H.J. PrSmel, A. Schrijver, Eds., Berlin: Springer-Verlag, 1990, pp. 267- 292.
	11	Neil Robertson , P D Seymour, Graph minors. V. Excluding a planar graph, Journal of Combinatorial Theory Series B, v.41 n.1, p.92-114, Aug. 1986 [doi>10.1016/0095-8956(86)90030-4]
	12	Neil Robertson , P. D. Seymour, Graph minors. XIII: the disjoint paths problem, Journal of Combinatorial Theory Series B, v.63 n.1, p.65-110, Jan. 1995 [doi>10.1006/jctb.1995.1006]
	13	Neil Robertson , Paul Seymour , Robin Thomas, Quickly excluding a planar graph, Journal of Combinatorial Theory Series B, v.62 n.2, p.323-348, Nov. 1994 [doi>10.1006/jctb.1994.1073]
	14	A. Schrijver, "Disjoint homotopic paths and trees in a planar graph," Discrete and Compuiaiional Geometry, 6(1991), pp. 527-574.
	15	A. Schrijver, "Homotopic routing methods," in Paths, Flows, and V~SI-~ayout, B. Korte, L. Lov~sz, H.J. PrSmel, A. Schrijver, Eds., Berlin: Springer- Verlag, 1990, pp. 329-372.
	16	Alexander Schrijver , Paul Seymour , Peter Winkler, The Ring Loading Problem, SIAM Journal on Discrete Mathematics, v.11 n.1, p.1-14, Feb. 1998 [doi>10.1137/S0895480195294994]
	17	A. Srinivasan, Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.416, October 19-22, 1997

CITED BY 9

	Venkatesan Guruswami , Sanjeev Khanna , Rajmohan Rajaraman , Bruce Shepherd , Mihalis Yannakakis, Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.19-28, May 01-04, 1999, Atlanta, Georgia, United States
	Venkatesan Guruswami , Sanjeev Khanna , Rajmohan Rajaraman , Bruce Shepherd , Mihalis Yannakakis, Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems, Journal of Computer and System Sciences, v.67 n.3, p.473-496, November 2003
	Petr Kolman , Christian Scheideler, Improved bounds for the unsplittable flow problem, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.184-193, January 06-08, 2002, San Francisco, California
	Chandra Chekuri , Sanjeev Khanna , F. Bruce Shepherd, Multicommodity flow, well-linked terminals, and routing problems, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Matthew Andrews , Lisa Zhang, Hardness of the undirected edge-disjoint paths problem, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Matthew Andrews , Lisa Zhang, Logarithmic hardness of the undirected edge-disjoint paths problem, Journal of the ACM (JACM), v.53 n.5, p.745-761, September 2006
	Ken-ichi Kawarabayashi , Bruce Reed, A nearly linear time algorithm for the half integral disjoint paths packing, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.446-454, January 20-22, 2008, San Francisco, California
	Ken-ichi Kawarabayashi, Half integral packing, Erdős-Posá-property and graph minors, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1187-1196, January 07-09, 2007, New Orleans, Louisiana
	Ken-ichi Kawarabayashi , Bruce Reed, A nearly linear time algorithm for the half integral parity disjoint paths packing problem, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1183-1192, January 04-06, 2009, New York, New York