A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs
A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs
复制标题
简单图中近乎最优的全对最小割算法
DOI：
10.1109/focs52979.2021.00111
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Thatchaphol Saranurak
中科院分区：
文献类型：
--
作者：
Jason Li;Debmalya Panigrahi;Thatchaphol Saranurak
本文给出了一<tex>个n^{2+o（1）}$</tex>时间算法，用于求<tex>n$</tex>个顶点上的简单无向图中所有顶点<tex>对s$</tex><tex>和t$的</tex><tex>s-t $</tex>最小割。我们通过在相同的运行时间内构建Gomory-Hu树（或割等价树）来实现这一点，从而改进了Abboud等人（STOC 2021）最近提出的<tex>$\tilde{O}（n^{2.5}）$的</tex>界。我们的运行时间几乎是<tex>n的最</tex>优函数。
We give an <tex>$n^{2+o(1)}$</tex>-time algorithm for finding <tex>$s-t$</tex> min-cuts for all pairs of vertices <tex>$s$</tex> and <tex>$t$</tex> in a simple, undirected graph on <tex>$n$</tex> vertices. We do so by constructing a Gomory-Hu tree (or cut equivalent tree) in the same running time, thereby improving on the recent bound of <tex>$\tilde{O}(n^{2.5})$</tex> by Abboud et al. (STOC 2021). Our running time is nearly optimal as a function of <tex>$n$</tex>.
多对数最大流中的确定性最小割
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