CAJ | 학술논문

最小饱和流问题就是求具有最小值的饱和流。此问题起源于紧急疏散和交通阻塞的研究，并且已知是一个NP-困难问题。本文探讨两个特殊情形：一个限定问题是寻求给定截集的最小饱和流，一个松弛问题是寻求最小双向容量截集。对于前者，通过构造一个辅助网络AN (S)及运用最大流算法，建立一个多项式时间算法，并证明其复杂性是O(n3)。对于后者，通过构造一个单向网络N′，将问题转化为一个最小容量截问题。但是这个新网络N′可能包含负容量的弧，一般不易求解。当单向网络N′是平面网络时，我们建立了多项式时间算法。
최소포화류문제취시구구유최소치적포화류。차문제기원우긴급소산화교통조새적연구，병차이지시일개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 traffc 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 polynomial-time 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.