Maximum Integer Flows in Directed Planar Graphs with Multiple Sources and Sinks and Vertex Capacities
Maximum Integer Flows in Directed Planar Graphs with Multiple Sources and Sinks and Vertex Capacities
复制标题
具有多个源、汇和顶点容量的有向平面图中的最大整数流
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Yipu Wang
中科院分区：
文献类型：
--
作者：
Yipu Wang
我们考虑在顶点和边都有容量的平面图中寻找最大流的问题，并考虑多个源和汇。当容量为整数时，我们提出了三种算法。第一个算法运行在$O（n log^3 n + kn）$时间当所有容量是有界的，其中$n$是图中的顶点数和$k$是终端数。该算法首次在近线性时间内解决了k有界但大于2的点不相交路径问题。时间复杂度为$O（k^2（k^3 + Delta）n ext{ polylog}（nU））$时间，其中$U$是单个顶点的最大有限容量，$Delta$是顶点的最大度。最后，当$k=3$，我们提出了一个算法，运行在$O（n log n）$时间，该算法的作品，即使当容量是任意实数。我们的算法提高了最快的已知算法时，$k$和$Delta$是小的，$U$是有界的多项式在$n$。在此结果之前，最快的算法对于真实的容量运行时间为O（n^2 / log n）$，对于整数容量运行时间为O（n^{3/2} log n log U）$。
We consider the problem of finding maximum flows in planar graphs with capacities on both vertices and edges and with multiple sources and sinks. We present three algorithms when the capacities are integers. The first algorithm runs in $O(n log^3 n + kn)$ time when all capacities are bounded, where $n$ is the number of vertices in the graph and $k$ is the number of terminals. This algorithm is the first to solve the vertex-disjoint paths problem in near-linear time when $k$ is bounded but larger than 2. The second algorithm runs in $O(k^2(k^3 + Delta) n ext{ polylog} (nU))$ time, where $U$ is the largest finite capacity of a single vertex and $Delta$ is the maximum degree of a vertex. Finally, when $k=3$, we present an algorithm that runs in $O(n log n)$ time; this algorithm works even when the capacities are arbitrary reals. Our algorithms improve on the fastest previously known algorithms when $k$ and $Delta$ are small and $U$ is bounded by a polynomial in $n$. Prior to this result, the fastest algorithms ran in $O(n^2 / log n)$ time for real capacities and $O(n^{3/2} log n log U)$ for integer capacities.