- 최대유통문제의 단수치명호 결정 방법
- ㆍ 저자명
- 정호연,안재근,박순달
- ㆍ 간행물명
- 韓國經營科學會誌
- ㆍ 권/호정보
- 2000년|25권 2호|pp.115-124 (10 pages)
- ㆍ 발행정보
- 한국경영과학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
The most vital arc in the maximum flow problem is that arc whose removal results in the greatest reduction in the value of the maximal flow between a source node and a sink node. This paper develops an algorithm to determine such a most vital arc in the maximum flow problem. We first define the transformed network corresponding to a given network in order to compute the minimal capacity for each candidate arc. The set of candidate arcs for single most vital arc consists of the arcs whose flow is at least as great as the flow over every arc in a minimal cut. As a result we present a method in which the most vital arc is determined more easily by computing the minimal capacity in the transformed network. the proposed method is demonstrated by numerical example and computational experiment.