2014/03/24 by Danupon Nanongkai, Nanongkai, Danupon
Computer Science · Engineering · #Advanced Graph Theory Research #Advanced Manufacturing and Logistics Optimization #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Digital Image Processing Techniques #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1403.6188
openalex publication_date 2014/03/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this short paper, we present an improved algorithm for approximating the\nminimum cut on distributed (CONGEST) networks. Let \λ be the minimum\ncut. Our algorithm can compute \λ exactly in\n\O((\√(n)+D) poly(\λ)) time, where n is the number of nodes\n(processors) in the network, D is the network diameter, and \O hides\n poly\log n. By a standard reduction, we can convert this algorithm into a\n(1+\ε)-approximation \O((\√(n)+D)/ poly(\ε))-time\nalgorithm. The latter result improves over the previous\n(2+\ε)-approximation \O((\√(n)+D)/ poly(\ε))-time\nalgorithm of Ghaffari and Kuhn [DISC 2013]. Due to the lower bound of\n\\Ω(\√(n)+D) by Das Sarma et al. [SICOMP 2013], this running\ntime is em tight up to a poly\log n factor. Our algorithm is an extremely\nsimple combination of Thorup's tree packing theorem [Combinatorica 2007],\nKutten and Peleg's tree partitioning algorithm [J. Algorithms 1998], and\nKarger's dynamic programming [JACM 2000].\n