文章基本信息

标题：A Simple Algorithm for Minimum Cuts in Near-Linear Time
本地全文：下载
作者：Nalin Bhardwaj ; Antonio J. Molina Lovett ; Bryce Sandlund 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：162
页码：12:1-12:18
DOI：10.4230/LIPIcs.SWAT.2020.12
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：minimum cut; sparsification; near-linear time; packing