文章基本信息

标题：Minimum Cut in O(m logÂ² n) Time
本地全文：下载
作者：PaweÅ, Gawrychowski ; Shay Mozes ; Oren Weimann 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：168
页码：57:1-57:15
DOI：10.4230/LIPIcs.ICALP.2020.57
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We give a randomized algorithm that finds a minimum cut in an undirected weighted m-edge n-vertex graph G with high probability in O(m logÂ² n) time. This is the first improvement to Kargerâs celebrated O(m logÂ³ n) time algorithm from 1996. Our main technical contribution is a deterministic O(m log n) time algorithm that, given a spanning tree T of G, finds a minimum cut of G that 2-respects (cuts two edges of) T.
关键词：Minimum cut; Minimum 2-respecting cut