Faster Cut-Equivalent Trees in Simple Graphs
Faster Cut-Equivalent Trees in Simple Graphs
复制标题
简单图中更快的等价割树
DOI：
10.4230/lipics.icalp.2022.109
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Tianyi Zhang
中科院分区：
文献类型：
--
作者：
Tianyi Zhang
设G =（V，E）是n阶无向连通简单图. G的割等价树是在同一顶点集V上的边加权树，使得对于任意一对顶点s，t ∈ V，该树的最小（s，t）-割也是G的最小（s，t）-割，且这两个割具有相同的割值。在最近的一篇论文[Abboud，Krauthgamer和Trabelsi，STOC 2021]中，作者提出了第一个用于构造割等价树的次立方时间算法。算法的时间复杂度为O（n）。5）运行时间。后来，这个运行时间被两个独立的作品[Abboud，Krauthgamer和Trabelsi，FOCS 2021]和[Li，Panigrahi，Saranurak，FOCS 2021]显着提高到n 2+ o（1），然后到（m + n 1）。9）1+ o（1）[Abboud，Krauthgamer和Trabelsi，SODA 2022]。在本文中，我们提高了运行时间的e O（n 2）图，如果近线性时间最大流算法存在，或e O（n 17 / 8）使用目前最快的最大流算法。虽然我们的算法是比以前的作品慢，运行时界变得更好的一个子多项式因子在密集的简单图时，假设近线性的时间最大流算法。
Let G = ( V, E ) be an undirected connected simple graph on n vertices. A cut-equivalent tree of G is an edge-weighted tree on the same vertex set V , such that for any pair of vertices s, t ∈ V , the minimum ( s, t )-cut in the tree is also a minimum ( s, t )-cut in G , and these two cuts have the same cut value. In a recent paper [Abboud, Krauthgamer and Trabelsi, STOC 2021], the authors propose the first subcubic time algorithm for constructing a cut-equivalent tree. More specifically, their algorithm has 1 e O ( n 2 . 5 ) running time. Later on, this running time was significantly improved to n 2+ o (1) by two independent works [Abboud, Krauthgamer and Trabelsi, FOCS 2021] and [Li, Panigrahi, Saranurak, FOCS 2021], and then to ( m + n 1 . 9 ) 1+ o (1) by [Abboud, Krauthgamer and Trabelsi, SODA 2022]. In this paper, we improve the running time to e O ( n 2 ) graphs if near-linear time max-flow algorithms exist, or e O ( n 17 / 8 ) using the currently fastest max-flow algorithm. Although our algorithm is slower than previous works, the runtime bound becomes better by a sub-polynomial factor in dense simple graphs when assuming near-linear time max-flow algorithms.
多对数最大流中的确定性最小割
DOI：
--
发表时间：
2020
期刊：
Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Li, Jason;Panigrahi, Debmalya
通讯作者：
Panigrahi, Debmalya
DOI：
10.1145/3357713.3384247
发表时间：
2019-10
期刊：
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Yang P. Liu;Aaron Sidford
通讯作者：
Yang P. Liu;Aaron Sidford