- 최대유통문제에서 MVA를 결정하는 방법에 관한 연구
- A Study on a Method of Determining the Most Vital Arc in the Maximum Flow Problem
- ㆍ 저자명
- 정호연
- ㆍ 간행물명
- 공업경영학회지
- ㆍ 권/호정보
- 1996년|19권 40호|pp.263-269 (7 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(MVA) in the maximum flow problem. We first define the transformed network corresponding In a given network in order to compute the minimal capacity for each candidate arc. The set of candidate arcs for a MVA consists of the arcs whose flow is at least as greate as the flow over every arc in a minimal cut As a result, we present a method in which the MVA is determined more easily by computing the minimal capacity in the transformed network. The proposed method is demonstrated by numerical example.