conference paper published yes Monika H Henzinger author 540c9bbd-f2de-11ec-812d-d04a5be856300000-0002-5008-6530 Satish Rao author Di Wang author SODA: Symposium on Discrete Algorithms We study the problem of computing a minimum cut in a simple, undirected graph and give a deterministic O(m log2 n log log2 n) time algorithm. This improves both on the best previously known deterministic running time of O(m log12 n) (Kawarabayashi and Thorup [12]) and the best previously known randomized running time of O(mlog3n) (Karger [11]) for this problem, though Karger's algorithm can be further applied to weighted graphs. Our approach is using the Kawarabayashi and Tho- rup graph compression technique, which repeatedly finds low-conductance cuts. To find these cuts they use a diffusion-based local algorithm. We use instead a flow- based local algorithm and suitably adjust their framework to work with our flow-based subroutine. Both flow and diffusion based methods have a long history of being applied to finding low conductance cuts. Diffusion algorithms have several variants that are naturally local while it is more complicated to make flow methods local. Some prior work has proven nice properties for local flow based algorithms with respect to improving or cleaning up low conductance cuts. Our flow subroutine, however, is the first that is both local and produces low conductance cuts. Thus, it may be of independent interest. Society for Industrial and Applied Mathematics2017Barcelona, Spain eng 1704.0125410.1137/1.9781611974782.125 1919-1938 https://research-explorer.ista.ac.at/record/11889 yes Henzinger M, Rao S, Wang D. 2017. Local flow partitioning for faster edge connectivity. 28th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1919–1938. Henzinger, M., Rao, S., &#38; Wang, D. (2017). Local flow partitioning for faster edge connectivity. In <i>28th Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 1919–1938). Barcelona, Spain: Society for Industrial and Applied Mathematics. <a href="https://doi.org/10.1137/1.9781611974782.125">https://doi.org/10.1137/1.9781611974782.125</a> Henzinger, Monika, Satish Rao, and Di Wang. “Local Flow Partitioning for Faster Edge Connectivity.” In <i>28th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 1919–38. Society for Industrial and Applied Mathematics, 2017. <a href="https://doi.org/10.1137/1.9781611974782.125">https://doi.org/10.1137/1.9781611974782.125</a>. Henzinger, Monika, et al. “Local Flow Partitioning for Faster Edge Connectivity.” <i>28th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Society for Industrial and Applied Mathematics, 2017, pp. 1919–38, doi:<a href="https://doi.org/10.1137/1.9781611974782.125">10.1137/1.9781611974782.125</a>. M. Henzinger, S. Rao, and D. Wang, “Local flow partitioning for faster edge connectivity,” in <i>28th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Barcelona, Spain, 2017, pp. 1919–1938. M. Henzinger, S. Rao, D. Wang, in:, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2017, pp. 1919–1938. Henzinger M, Rao S, Wang D. Local flow partitioning for faster edge connectivity. In: <i>28th Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Society for Industrial and Applied Mathematics; 2017:1919-1938. doi:<a href="https://doi.org/10.1137/1.9781611974782.125">10.1137/1.9781611974782.125</a> 118732022-08-16T12:20:59Z2024-11-06T12:22:42Z