论文标题
有关最低切割算法的注释
A Note on a Recent Algorithm for Minimum Cut
论文作者
论文摘要
给定带有$ m $边缘和$ n $ dertices的无向边缘加权图$ g =（v，e）$，最小切割问题要求找到一个$ s $ s $的子集，以使所有边缘的总重量在$ s $ s $和$ v \ setminus s $之间的总重量很小。 Karger的长期$ O（M \ log^3 n）$ $ o（M \ log^2 n）$ [icalp'20]和$ o（m \ log^2 n + n + n \ log^5 n）$最近在两项独立的作品中得到了时间随机算法的改进。这两种算法使用不同的方法和技术。特别是，虽然前者更快，但后者的优点是可以用来在切割质量和计算模型中获得有效的算法。在本文中，我们展示了如何简化和改进[stoc'20]的算法到$ O（m \ log^2 n + n + n \ log^3 n）$。我们通过替换一个随机算法来获得此消息，该算法在给定的树$ t $ $ g $的情况下，在$ o（m \ log n+n+n+n \ log^4 n）$ time中找到了2个倍率的$ g $的最小切割（切成两个$ t $ t $）的简单$ o（m \ log n+n+n+log^2 n $ nime consimistians al nimistians al nimistians andimistion nm andimistion nm andimistion nm andimistion nm andimistion nm andimistion nm nmitistion。
Given an undirected edge-weighted graph $G=(V,E)$ with $m$ edges and $n$ vertices, the minimum cut problem asks to find a subset of vertices $S$ such that the total weight of all edges between $S$ and $V \setminus S$ is minimized. Karger's longstanding $O(m \log^3 n)$ time randomized algorithm for this problem was very recently improved in two independent works to $O(m \log^2 n)$ [ICALP'20] and to $O(m \log^2 n + n\log^5 n)$ [STOC'20]. These two algorithms use different approaches and techniques. In particular, while the former is faster, the latter has the advantage that it can be used to obtain efficient algorithms in the cut-query and in the streaming models of computation. In this paper, we show how to simplify and improve the algorithm of [STOC'20] to $O(m \log^2 n + n\log^3 n)$. We obtain this by replacing a randomized algorithm that, given a spanning tree $T$ of $G$, finds in $O(m \log n+n\log^4 n)$ time a minimum cut of $G$ that 2-respects (cuts two edges of) $T$ with a simple $O(m \log n+n\log^2 n)$ time deterministic algorithm for the same problem.
