2026-08-02T02:47:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12259 2024-03-06T10:49:28Z ddc:004 open_access

A Simple Algorithm for Minimum Cuts in Near-Linear Time Bhardwaj, Nalin Molina Lovett, Antonio J. Sandlund, Bryce minimum cut sparsification near-linear time packing We consider the minimum cut problem in undirected, weighted graphs. We give a simple algorithm to find a minimum cut that 2-respects (cuts two edges of) a spanning tree T of a graph G. This procedure can be used in place of the complicated subroutine given in Karger’s near-linear time minimum cut algorithm [Karger, 2000]. We give a self-contained version of Karger’s algorithm with the new procedure, which is easy to state and relatively simple to implement. It produces a minimum cut on an m-edge, n-vertex graph in O(m log³ n) time with high probability, matching the complexity of Karger’s approach. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nalin Bhardwaj and Antonio J. Molina Lovett and Bryce Sandlund 2020 Is Part Of LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2020.12 urn:nbn:de:0030-drops-122594 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.12 eng https://creativecommons.org/licenses/by/3.0/legalcode