论文标题
用于计算未指向未加权平面图中最大流量活力的线性时间算法
A Linear Time Algorithm for Computing Max-Flow Vitality in Undirected Unweighted Planar Graphs
论文作者
论文摘要
图中边缘在两个固定顶点$ s $和$ t $之间的最大流量中的生命力定义为减少由于去除该边缘而导致的最大流动值。 最大流量的生命力问题已经有效地解决了$ st $ - 平面图，但对于一般平面图仍未开放。我们的结果首次为通用平面图提供了最佳解决方案，尽管仅限于未加权平面图的情况。
The vitality of an edge in a graph with respect to the maximum flow between two fixed vertices $s$ and $t$ is defined as the reduction of the maximum flow value caused by the removal of that edge. The max-flow vitality problem has already been efficiently solved for $st$-planar graphs but has remained open for general planar graphs. For the first time our result provides an optimal solution for general planar graphs although restricted to the case of unweighted planar graphs.
