Maximum Flow in Directed Planar Graphs with Vertex Capacities
Maximum Flow in Directed Planar Graphs with Vertex Capacities
复制标题
具有顶点容量的有向平面图中的最大流
DOI：
10.1007/s00453-010-9436-7
复制
发表时间：
2009
期刊：
影响因子：
1.1
通讯作者：
Yahav Nussbaum
中科院分区：
文献类型：
--
作者：
Haim Kaplan;Yahav Nussbaum
在本文中，我们提出了一个O（nlog n）的时间算法寻找一个最大流的有向平面图，其中的顶点受到容量约束，除了弧。如果源和汇在同一个面上，那么我们的算法可以在O（n）时间内实现。对于一般的（非平面的）图，顶点容量不会使最大流问题变得更困难，因为有一个简单的约简消除了顶点容量。然而，这种减少并不能保持图形的平面性。我们的算法的本质是一个不同的减少，并保持平面性，可以在线性时间内实现。对于无向平面图的特殊情况，最近有人提出了一个具有相同时间复杂度的算法，但我们证明了它有一个缺陷，我们还应用我们的技术得到了一个线性时间算法，以将流转换为无环流，和一个线性时间算法，以找到一个最大的顶点不相交的s-t路径，在有向平面图。
In this paper we present an O(nlog n) time algorithm for finding a maximum flow in a directed planar graph, where the vertices are subject to capacity constraints, in addition to the arcs. If the source and the sink are on the same face, then our algorithm can be implemented in O(n) time.For general (not planar) graphs, vertex capacities do not make the maximum flow problem more difficult, as there is a simple reduction that eliminates vertex capacities. However, this reduction does not preserve the planarity of the graph. The essence of our algorithm is a different reduction that does preserve the planarity and can be implemented in linear time. For the special case of undirected planar graphs, an algorithm with the same time complexity was recently claimed, but we show that it has a flaw.We also apply our technique to obtain a linear-time algorithm to convert a flow to an acyclic flow, and a linear-time algorithm to find a largest set of vertex-disjoint s−t paths, in a directed planar graph.