Publication
Journal of the ACM
Paper

Graph partitioning using single commodity flows

View publication

Abstract

We show that the sparsest cut in graphs with n vertices and m edges can be approximated within O(log 2 n) factor in (m + n 3/2) time using polylogarithmic single commodity max-flow computations. Previous algorithms are based on multicommodity flows that take time (m + n 2). 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 2 n)-(pseudo-) approximation algorithm for the edge-separator problem with a similar running time. © 2009 ACM.

Date

Publication

Journal of the ACM

Authors

Topics

Share