Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer
ISSN : 2005-0461(Print)
ISSN : 2287-7975(Online)
Journal of Society of Korea Industrial and Systems Engineering Vol.19 No.40 pp.263-269
DOI :

최대유통문제에서 MVA를 결정하는 방법에 관한 연구

정효연
전주대학교 산업공학과

A Study on a Method of Determining the Most Vital Arc in the Maximum Flow Problem


[$AuthorMark7$]

Abstract

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.

Reference