Parametric min-cuts analysis in a network ?
The all pairs minimum cuts problem in a capacitated undirected network is well known. Gomory and Hu showed that the all pairs minimum cuts are revealed by a min-cut tree that can be obtained by solving exactly (n?1) maximum flow problems, where n is the number of nodes in the network. In this paper we consider first the problem of finding parametric min-cuts for a specified pair of nodes when the capacity of an arc i is given by min{bi,?}, where ? is the parameter, ranging from 0 to ?. Next we seek the parametric min-cuts for all pairs of nodes, and achieve this by constructing min-cut trees for at most 2m different values of ?, where m is the number of edges in the network.
multiterminal maximal flows parametric analysis combinatorial optimization