We study the problem of computing the vitality of edges and vertices with respect to the $st$-max flow in undirected planar graphs, where the vitality of an edge/vertex is the $st$-max flow decrease when the edge/vertex is removed from the graph. This allows us to establish the vulnerability of the graph with respect to the $st$-max flow. We give efficient algorithms to compute an additive guaranteed approximation of the vitality of edges and vertices in planar undirected graphs. We show that in the general case high vitality values are well approximated in time close to the time currently required to compute $st$-max flow $O(n\log\log n)$. We also give improved, and sometimes optimal, results in the case of integer capacities. All our algorithms work in $O(n)$ space.
翻译:我们研究了在未定向平面图中计算边缘和顶脊的活力的问题,在未定向平面图中,边缘/顶点的活力是当边缘/顶点从图中去除时的美元-最大流量下降。这使我们能够确定图表相对于美元-最大流量的脆弱性。我们提供了高效的算法,以计算在平面非定向图中边缘和顶点的活力的附加保证近似值。我们表明,在一般情况下,高活力值非常接近目前计算美元-最大流量所需的时间(O美元(n\log\log n)美元)。我们还提供了改进,有时是最佳的结果,以整数能力为例。我们的所有算法都在$O(n) 的范围内工作。