Liya Fan, Fa Zhang, et al.
JPDC
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.
Liya Fan, Fa Zhang, et al.
JPDC
Conrad Albrecht, Jannik Schneider, et al.
CVPR 2025
Yehuda Naveli, Michal Rimon, et al.
AAAI/IAAI 2006
Ran Iwamoto, Kyoko Ohara
ICLC 2023