Approximate max-flow min-(multi)cut theorems and their applications

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximate max-flow min-(multi)cut theorems and their applications

Full text

Pdf (967 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 698 - 707

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

Naveen Garg
Vijay V. Vazirani
Mihalis Yannakakis

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 16, Downloads (12 Months): 120, Citation Count: 13

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/167088.167266 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	W. H. Cunningham (1991), "The optimal multiterminal cut problem", DIMACS Series zn Disc. Math. and Theor. Comput. Sci. 5 (1991), pp. 105-120.
	2	E. Dahlhaus , D. S. Johnson , C. H. Papadimitriou , P. D. Seymour , M. Yannakakis, The complexity of multiway cuts (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.241-251, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129736]
	3	P. Elias, A. Feinstein and C.E. Shannon (1956), "A note on the maximum flow through a network , IRE Transactions on Information Theory IT 2 (1956), pp. 117-119.
	4	L.R. Ford, Jr. and D.R. Fulkerson (1956), "Maximal flow through a network", Canadian Journal of Matherr#ati~# 8 (195G).
	5	N. Garg and V. V. Vazirani, "A polyhedron with all s-t cuts as vertices, and adjacency of cuts", Proceedings, 3rd Integer Programming and Combinatorial Optimization Conference (1993).
	6	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
	7	T.C. Hu (1963), "Multicommodity network flows", Operations Research 11 (1963), pp. 344-360.
	8	P. Klein, A. Agrawal, R. Ravi and S. Rao (1990), "Approximation through multicommodity flow", Proceedings, 31#t Symposium on Foundations of Computer Science (1990), pp. 726-737.
	9	Philip Klein , Serge A. Plotkin , Satish Rao, Excluded minors, network decomposition, and multicommodity flow, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.682-690, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167261]
	10	P. Klein , C. Stein , É. Tardos, Leighton-Rao might be practical: faster approximation algorithms for concurrent flow with uniform capacities, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.310-321, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100257]
	11	F.T. Leighton and S. Rao (1988), "An approximate max-flow rain-cut theorem for uniform multicommodity flow problems with application to approximation algorithms", Proceedings, 29th Symposium on Foundations of Computer Science (1988), pp. 422-431.
	12	Serge A. Plotkin , Éva Tardos, Improved bounds on the max-flow min-cut ratio for multicommodity flows, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.691-697, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167263]
	13	E. Tardos and V. V. Vazirani, "Improved bounds for the max-flow min-multicut ratio for planar and K#,#- free graphs", submitted }or publication (1992).
	14	Spyros Tragoudas, VLSI partitioning approximation algorithms based on multicommodity flow and other techniques, University of Texas at Dallas, Richardson, TX, 1991
	15	M. Yannakakis (19Sl), "Edge-Deletion problems", SIAM Journal of Computing 10 (19Sl), pp. 77-79.
	16	Mihalis Yannakakis , Paris C. Kanellakis , Stavros S. Cosmadakis , Christos H. Papadimitriou, Cutting and Partitioning a Graph aifter a Fixed Pattern (Extended Abstract), Proceedings of the 10th Colloquium on Automata, Languages and Programming, p.712-722, July 18-22, 1983

CITED BY 13

	Gruia Calinescu , Howard Karloff , Yuval Rabani, Approximation algorithms for the 0-extension problem, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.8-16, January 07-09, 2001, Washington, D.C., United States
	Guy Even , Joseph (Seffi) Naor , Satish Rao , Baruch Schieber, Fast approximate graph partitioning algorithms, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.639-648, January 05-07, 1997, New Orleans, Louisiana, United States
	Serge A. Plotkin , Éva Tardos, Improved bounds on the max-flow min-cut ratio for multicommodity flows, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.691-697, May 16-18, 1993, San Diego, California, United States
	Sanjeev Arora, The approximability of NP-hard problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.337-348, May 24-26, 1998, Dallas, Texas, United States
	Moses Charikar , Chandra Chekuri , Ashish Goel , Sudipto Guha, Rounding via trees: deterministic approximation algorithms for group Steiner trees and k-median, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.114-123, May 24-26, 1998, Dallas, Texas, United States
	Philip Klein , Serge A. Plotkin , Satish Rao, Excluded minors, network decomposition, and multicommodity flow, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.682-690, May 16-18, 1993, San Diego, California, United States
	Daniel Golovin , Viswanath Nagarajan , Mohit Singh, Approximating the k-multicut problem, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.621-630, January 22-26, 2006, Miami, Florida
	Kenji Obata, Approximate max-integral-flow/min-multicut theorems, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Amit Agarwal , Moses Charikar , Konstantin Makarychev , Yury Makarychev, O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	David S. Johnson, The NP-completeness column: The many limits on approximation, ACM Transactions on Algorithms (TALG), v.2 n.3, p.473-489, July 2006
	Julia Chuzhoy , Sanjeev Khanna, Hardness of cut problems in directed graphs, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Ittai Abraham , Yair Bartal , Ofer Neimany, Advances in metric embedding theory, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Julia Chuzhoy , Sanjeev Khanna, Polynomial flow-cut gaps and hardness of directed cut problems, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA