Memoirs of the Faculty of Science, Shimane University

number of downloads : ?
Memoirs of the Faculty of Science, Shimane University 25
1991-12-25 発行

無限ネットワーク上のマキシミニ切断問題

A Maximin Cut Problem on a Infinite Network
Yamasaki, Maretsugu
File
Description
The study of duality relations between the max-flow problems and the min-cut problems seems to be one of the most important themes in the theory ofnetworks. On a finite network, the celebrated max-flow min-cut theorem due to Ford and Fulkerson [2] has been the unique result for this direction before the work of Strang [6]. On an infinite network, Yamasaki [7] and Nakamura and Yamasaki[4] gave several max-flow min-cut theorems related to several kinds of flows and cuts. In this paper, we shall introduce a notion of an exceptional set of cuts with respect to the extremal width and consider a maximin cut problem. It will be shown by using the penalty method that the value of this maximin problem is equal to thevalue of a max-flow problem.
For notation and terminology, we mainly follow [3] and [5].