Deterministic mincut in almost-linear time
Deterministic mincut in almost-linear time
复制标题
几乎线性时间内的确定性最小割
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Jason Li
中科院分区：
文献类型：
--
作者：
Jason Li
我们提出了一个确定性（全局）最小切算法，用于在m1+o(1)时间内运行的加权无向图，回答了20世纪90年代的一个开放问题。为了得到我们的结果，我们将Karger的近线性时间最小切算法中骨架图的构造去随机化，这是它唯一的随机化成分。特别地，我们通过随机抽样部分地去随机化著名的本丘-格图稀疏化技术，这是我们通过悲观估计器的方法完成的。我们的主要技术组件是设计一个有效的悲观估计器来捕获图的切割，这涉及利用Goranci等人（SODA 2021）在最近的工作中引入的扩展分解框架。作为一个副作用，我们获得了图中所有近似最小切的结构表示，这可能有未来的应用。
We present a deterministic (global) mincut algorithm for weighted, undirected graphs that runs in m1+o(1) time, answering an open question of Karger from the 1990s. To obtain our result, we de-randomize the construction of the skeleton graph in Karger’s near-linear time mincut algorithm, which is its only randomized component. In particular, we partially de-randomize the well-known Benczur-Karger graph sparsification technique by random sampling, which we accomplish by the method of pessimistic estimators. Our main technical component is designing an efficient pessimistic estimator to capture the cuts of a graph, which involves harnessing the expander decomposition framework introduced in recent work by Goranci et al. (SODA 2021). As a side-effect, we obtain a structural representation of all approximate mincuts in a graph, which may have future applications.
多对数最大流中的确定性最小割
DOI：
--
发表时间：
2020
期刊：
Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Li, Jason;Panigrahi, Debmalya
通讯作者：
Panigrahi, Debmalya
用于平衡切割的确定性算法及其在动态连接、流等方面的应用
DOI：
10.1109/focs46700.2020.00111
发表时间：
2020
期刊：
2020
影响因子：
--
作者：
Chuzhoy, Julia;Gao, Yu;Li, Jason;Nanongkai, Danupon;Peng, Richard;Saranurak, Thatchaphol
通讯作者：
Saranurak, Thatchaphol