Improved bounds on the max-flow min-cut ratio for multicommodity flows

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improved bounds on the max-flow min-cut ratio for multicommodity flows

Full text

Pdf (569 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: 691 - 697

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

Serge A. Plotkin
Éva Tardos

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 25, Citation Count: 5

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.167263 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	L. R. Ford, Jr. and D. R. Fulkerson. Flows in Networks. Princeton Univ. Press, Princeton, NJ, 1962.
	2	Naveen Garg , Vijay V. Vazirani , Mihalis Yannakakis, Approximate max-flow min-(multi)cut theorems and their applications, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.698-707, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167266]
	3	P. Klein, S. Plotkin, and S. Rao. Planar graphs, multicommodity flow, and network decomposition. In this Proceedings.
	4	P. N. Klein, S. Rao, A. Agrawal, and R. Ravi. An approximate max-flow min-cut relation for multicommodity flow, with applications. Submitted to Combinatorica (1992). Preliminary version appeared as "Approximation through multicommodity flow," In Proc. 31th IEEE Annual Symposium on Foundations of Computer Science, pages 726-727, 1990.
	5	Tom Leighton , Clifford Stein , Fillia Makedon , Éva Tardos , Serge Plotkin , Spyros Tragoudas, Fast approximation algorithms for multicommodity flow problems, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.101-111, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103425]
	6	T. Leighton and S. Rao. An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In Proc. 2#rh IEEEAnnual Symposium on Foundations of Computer Science, pages 422- 431, 1988.
	7	Spyros Tragoudas, VLSI partitioning approximation algorithms based on multicommodity flow and other techniques, University of Texas at Dallas, Richardson, TX, 1991

CITED BY 5

	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
	Naveen Garg , Vijay V. Vazirani , Mihalis Yannakakis, Approximate max-flow min-(multi)cut theorems and their applications, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.698-707, May 16-18, 1993, San Diego, California, United States
	Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999
	Gruia Calinescu , Cristina G. Fernandes , Bruce Reed, Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width, Journal of Algorithms, v.48 n.2, p.333-359, September 2003
	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