最小饱和流问题的多项式时间可解变形(英文)

Polynomial Time Solvable Variants of the Minimum Saturated Flow Problem

最小饱和流问题就是求具有最小值的饱和流.此问题起源于紧急疏散和交通阻塞的研究,并且已知是一个NP-困难问题.本文探讨两个特殊情形:一个限定问题是寻求给定截集的最小饱和流,一个松弛问题是寻求最小双向容量截集.对于前者,通过构造一个辅助网络AN(S)及运用最大流算法,建立一个多项式时间算法,并证明其复杂性是O(n3).对于后者,通过构造一个单向网络N′,将问题转化为一个最小容量截问题.但是这个新网络N′可能包含负容量的弧,一般不易求解.当单向网络N′是平面网络时,我们建立了多项式时间算法.

The minimum saturated flow problem is to find a saturated flow with minimum value,which arises from the study of emergency evacuation and traffic block,and it is known to be NP-hard.This paper studies two special cases： a restricted problem of finding minimum saturated flow with a given cut and a relaxation problem of finding minimum two-way capacity cut.For the former,we present a polynomialtime algorithm by constructing an auxiliary network and using the maximum flow algorithm.The complexity of the algorithm is proved to be O（n3）.For the latter,we transform the problem into a minimum capacity cut problem by constructing a one-way network N′.However,it is not easy to be solved because the network N′may include negative capacity arcs.A polynomial-time algorithm is presented when the one-way network N′is planar.