{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T10:19:15Z","timestamp":1781259555740,"version":"3.54.1"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2009,6,1]],"date-time":"2009-06-01T00:00:00Z","timestamp":1243814400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,6]]},"abstract":"<jats:p>\n            We show that the sparsest cut in graphs with\n            <jats:italic>n<\/jats:italic>\n            vertices and\n            <jats:italic>m<\/jats:italic>\n            edges can be approximated within\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) factor in \u00d5(\n            <jats:italic>m<\/jats:italic>\n            + n\n            <jats:sup>3\/2<\/jats:sup>\n            ) time using polylogarithmic single commodity max-flow computations. Previous algorithms are based on multicommodity flows that take time \u00d5(\n            <jats:italic>m<\/jats:italic>\n            + n\n            <jats:sup>2<\/jats:sup>\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\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            )-(pseudo-) approximation algorithm for the edge-separator problem with a similar running time.\n          <\/jats:p>","DOI":"10.1145\/1538902.1538903","type":"journal-article","created":{"date-parts":[[2009,6,30]],"date-time":"2009-06-30T13:10:17Z","timestamp":1246367417000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":57,"title":["Graph partitioning using single commodity flows"],"prefix":"10.1145","volume":"56","author":[{"given":"Rohit","family":"Khandekar","sequence":"first","affiliation":[{"name":"IBM Thomas J. Watson Research Center, Hawthorne, New York"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Satish","family":"Rao","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Umesh","family":"Vazirani","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,7,2]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"Ahuja R.","year":"1993","unstructured":"Ahuja , R. , Magnati , T. , and Orlin , J . 1993 . Network Flows: Theory, Algorithms, and Applications . Prentice Hall , Eaglewood Cliffs . Ahuja, R., Magnati, T., and Orlin, J. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Eaglewood Cliffs."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90092-9"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250823"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007355"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794285983"},{"key":"e_1_2_1_7_1","volume-title":"Flavors of Geometry","author":"Ball K.","unstructured":"Ball , K. 1997. An elementary introduction to modern convex geometry . In Flavors of Geometry , S. Levy, Ed. Cambridge University Press , Cambridge , 1--58. Ball, K. 1997. An elementary introduction to modern convex geometry. In Flavors of Geometry, S. Levy, Ed. Cambridge University Press, Cambridge, 1--58."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237827"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.175.0420"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199355754"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, 300--309","author":"Garg N.","unstructured":"Garg , N. , and K\u00f6nemann , J . 1998. Faster and simpler algorithms for multicommodity flow and other fractional packing problems . In Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, 300--309 . Garg, N., and K\u00f6nemann, J. 1998. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, 300--309."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290181"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0916028"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/266021.266273"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the Neural Information Processing Systems.","author":"Lang K.","year":"2005","unstructured":"Lang , K. 2005 . Fixing two weaknesses of the spectral method . In Proceedings of the Neural Information Processing Systems. Lang, K. 2005. Fixing two weaknesses of the spectral method. In Proceedings of the Neural Information Processing Systems."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Lang K.","unstructured":"Lang , K. , and Rao , S . 1993. Finding near-optimal cuts: An empirical evaluation . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. ACM , New York, 212--221. Lang, K., and Rao, S. 1993. Finding near-optimal cuts: An empirical evaluation. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 212--221."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the MPS Conference on Integer Programming and Combinatorial Optimization. 325--337","author":"Lang K.","unstructured":"Lang , K. , and Rao , S . 2004. A flow-based method for improving the expansion or conductance of graph cuts . In Proceedings of the MPS Conference on Integer Programming and Combinatorial Optimization. 325--337 . Lang, K., and Rao, S. 2004. A flow-based method for improving the expansion or conductance of graph cuts. In Proceedings of the MPS Conference on Integer Programming and Combinatorial Optimization. 325--337."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200757"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73060"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374442"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0611030"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0605030"},{"key":"e_1_2_1_28_1","unstructured":"Walshaw C. 2000. The graph partitioning archive. http:\/\/staffweb.cms.gre.ac.uk\/~wc06\/partition\/.  Walshaw C. 2000. The graph partitioning archive. http:\/\/staffweb.cms.gre.ac.uk\/~wc06\/partition\/."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1538902.1538903","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1538902.1538903","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:53Z","timestamp":1750278413000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1538902.1538903"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,6]]}},"alternative-id":["10.1145\/1538902.1538903"],"URL":"https:\/\/doi.org\/10.1145\/1538902.1538903","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,6]]},"assertion":[{"value":"2006-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-07-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}