论文标题
未向未加权的平面图中的最大流量活力
Max-flow vitality in undirected unweighted planar graphs
论文作者
论文摘要
我们显示了一种快速算法，用于确定平面未取得的未加权图中的边缘集，其删除降低了两个固定顶点之间的最大流量。这是最大流动性问题的一种特殊情况，该案例已有效地用于一般的无向图和ST平面图。图相对于两个固定顶点S和T之间的最大流量的边缘的活力定义为降低了该边缘的去除而导致的最大流量。在本文中，我们表明，在平面未指向的未加权图中，具有大于零的边缘的边缘可以在O（n log n）最差的时间和o（n）空间中找到。
We show a fast algorithm for determining the set of edges in a planar undirected unweighted graph, whose deletion reduces the maximum flow between two fixed vertices. This is a special case of the max flow vitality problem, that has been efficiently solved for general undirected graphs and st-planar graphs. The vitality of an edge of a graph with respect to the maximum flow between two fixed vertices s and t is defined as the reduction of the maximum flow caused by the removal of that edge. In this paper we show that the set of edges having vitality greater than zero in a planar undirected unweighted graph with n vertices can be found in O(n log n) worst-case time and O(n) space.
