Min st-cut Oracle for Planar Graphs with Near-Linear Preprocessing Time
Min st-cut Oracle for Planar Graphs with Near-Linear Preprocessing Time
复制标题
用于具有近线性预处理时间的平面图的最小 st-cut Oracle
DOI：
10.1145/2684068
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Christian Wulff
中科院分区：
文献类型：
--
作者：
G. Borradaile;P. Sankowski;Christian Wulff
对于具有非负边权重的无向 $n$ 顶点平面图 $G$，我们考虑以下类型的查询：给定 $G$ 中的两个顶点 $s$ 和 $t$，$G$ 中最小 $st$-cut 的权重是多少？我们展示了如何使用 $O(n\log^5n)$ 预处理时间和 $O(n\log n)$ 空间在恒定时间内回答此类查询。我们使用 Gomory-Hu 树来隐式地表示所有成对的最小 $st$ 切割。此前，尚无解决该问题的次二次时间算法。我们的预言机可以扩展为报告与规模成正比的时间的最小 $st$ 削减。由于所有对 min $st$-cut 和最小循环基是平面图中的对偶问题，因此我们还获得了 $O(n\log^5n)$ 时间和 $O(n\log n)$ 空间中最小循环基的隐式表示，以及具有额外 $O(C)$ 时间和空间的显式表示，其中 $C$ 是基的大小。为了获得我们的结果，我们要求最短路径是唯一的，可以通过额外的 $O(\log^2 n)$ 运行时间因子确定性地消除这个假设。
For an undirected $n$-vertex planar graph $G$ with non-negative edge-weights, we consider the following type of query: given two vertices $s$ and $t$ in $G$, what is the weight of a min $st$-cut in $G$? We show how to answer such queries in constant time with $O(n\log^5n)$ preprocessing time and $O(n\log n)$ space. We use a Gomory-Hu tree to represent all the pair wise min $st$-cuts implicitly. Previously, no sub quadratic time algorithm was known for this problem. Our oracle can be extended to report the min $st$-cuts in time proportional to their size. Since all-pairs min $st$-cut and the minimum cycle basis are dual problems in planar graphs, we also obtain an implicit representation of a minimum cycle basis in $O(n\log^5n)$ time and $O(n\log n)$ space and an explicit representation with additional $O(C)$ time and space where $C$ is the size of the basis. To obtain our results, we require that shortest paths be unique, this assumption can be removed deterministically with an additional $O(\log^2 n)$ running-time factor.