Access Restriction

Author Khandekar, Rohit ♦ Rao, Satish ♦ Vazirani, Umesh
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2009
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Edge-separator ♦ Single commodity max-flow ♦ Sparse cut ♦ Spectral method
Abstract We show that the sparsest cut in graphs with $\textit{n}$ vertices and $\textit{m}$ edges can be approximated within $O(log^{2}$ $\textit{n})$ factor in $Õ(\textit{m}$ + $n^{3/2})$ time using polylogarithmic single commodity max-flow computations. Previous algorithms are based on multicommodity flows that take time $Õ(\textit{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}$ $\textit{n})-(pseudo-)$ approximation algorithm for the edge-separator problem with a similar running time.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2009-07-02
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 56
Issue Number 4
Page Count 15
Starting Page 1
Ending Page 15

Open content in new tab

   Open content in new tab
Source: ACM Digital Library