PARAMETRIC MAX-FLOW PROBLEMS IN A CLASS OF NETWORKS WITH SERIES-PARALLEL STRUCTURE

This paper considers a parametric max flow network problem where arc c apacities are not fixed but stated as unknown variables to be determin ed optimally such that the corresponding max flow satisfies flow requi rement between source and sink. For the problem, a max flow algorithm may be adapted as a subroutine to be used recursively in an enumerativ e solution search until finding the optimal solution. However, such an enumerative approach is not practical because it is not guaranteed to solve the problem in a finite number of steps. Therefore, this paper pays attention to the instance defined in a special class of networks, called basically-series-parallel networks, for which all minimal cuts ets can easily be enumerated in polynomial time by introducing a set o f network reduction methods, called 2-neighbor-node, parallel and sour ce-delta reductions, while such minimal cutset enumeration itself is N P-hard in general. Once all minimal cutsets are found, the associated parametric max flow problem remains simply to solve in a linear progra mming approach.