论文标题
关于最大流动的无向平面图有多脆弱
How Vulnerable is an Undirected Planar Graph with respect to Max Flow
论文作者
论文摘要
我们研究了在无向平面图中计算边缘和顶点的生命力相对于$ st $ -max流的问题，其中边缘/顶点的活力是从图中删除边缘/顶点时$ st $ -max流量的降低。这使我们能够建立图形相对于$ st $ -max流的漏洞。 我们提供有效的算法来计算平面无向图中边缘和顶点的添加剂保证的近似。我们表明，在一般情况下，高活力值在近似于计算$ st $ -max流量$ o（n \ log \ log n）$的时间接近的时间。在整数容量的情况下，我们还提供了改进，有时甚至最佳的结果。我们所有的算法在$ O（n）$空间中工作。
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.
