Graph partitioning using single commodity flows

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Graph partitioning using single commodity flows

Full text

Pdf (131 KB)

Source

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

Seattle, WA, USA

SESSION: Session 10A table of contents

Pages: 385 - 390

Year of Publication: 2006

ISBN:1-59593-134-1

Authors

Rohit Khandekar	University of Waterloo, Canada
Satish Rao	University of California, Berkeley
Umesh Vazirani	University of California, Berkeley

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	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/1132516.1132574 What is a DOI?

ABSTRACT

We show that the sparsest cut in graphs can be approximated within O(log² n) factor in Õ(n^3/2) time using polylogarithmic single commodity max-flow computations. Previous algorithms are based on multicommodity flows which take time Õ(n²). Our algorithm iteratively employs max-flow computations to embed an expander flow, thus providing a certificate of expansion. Our technique can also be extended to yield an O(log² n) (pseudo) approximation algorithm for the edge-separator problem with a similar running time.

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	Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
	2	N. Alon and V. Milman. λ1, isoperimetric inequalities for graphs, and superconcentrators. Journal of Combinatorial Theory, Series B, 38:73--88, 1985.
	3	Sanjeev Arora , Elad Hazan , Satyen Kale, 0(\sqrt {\log n)} Approximation to SPARSEST CUT in Õ(n²) Time, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.238-247, October 17-19, 2004 [doi>10.1109/FOCS.2004.1]
	4	Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.222-231, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007355]
	5	András A. Benczúr , David R. Karger, Approximating s-t minimum cuts in Õ(n²) time, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.47-55, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237827]
	6	W. Donath and A. J. Hoffman. Lower bounds for partitioning of graphs. IBM J. Res. Develop., 17:420--425, 1973.
	7	Andrew V. Goldberg , Satish Rao, Beyond the flow decomposition barrier, Journal of the ACM (JACM), v.45 n.5, p.783-797, Sept. 1998 [doi>10.1145/290179.290181]
	8	Bruce Hendrickson , Robert Leland, An improved spectral graph partitioning algorithm for mapping parallel computations, SIAM Journal on Scientific Computing, v.16 n.2, p.452-469, March 1995 [doi>10.1137/0916028]
	9	George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: application in VLSI domain, Proceedings of the 34th annual conference on Design automation, p.526-529, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266273]
	10	George Karypis , Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [doi>10.1137/S1064827595287997]
	11	B. Kernighan and S. Lin. An effective heuristic procedure for partitioning graphs. The Bell System Technical Journal, pages 291--308, 1970.
	12	K. Lang. Finding good nearly balanced cuts in power law graphs. Manuscript, 2004.
	13	Kevin Lang , Satish Rao, Finding near-optimal cuts: an empirical evaluation, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.212-221, January 25-27, 1993, Austin, Texas, United States
	14	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 [doi>10.1145/331524.331526]
	15	Alex Pothen , Horst D. Simon , Kan-Pu Liou, Partitioning sparse matrices with eigenvectors of graphs, SIAM Journal on Matrix Analysis and Applications, v.11 n.3, p.430-452, Jul. 1990 [doi>10.1137/0611030]
	16	Daniel A. Spielman , Shang-Hua Teng, Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007372]
	17	R. Tanner. Explicit concentrators from generalized n-gons. SIAM J. Alg. Disc. Methods, 5:287--293, 1984.