DISCONNECTING SETS IN SINGLE AND 2-TERMINAL-PAIR NETWORKS

We consider mixed networks, which may include both directed and undire cted edges. For a nontrivial vertex subset S, an S-disconnecting set i s a set of edges and vertices which intersects every path from any ver tex in S to any vertex not in S. Given nonnegative edge and vertex cos ts, we show that the minimum cost of an S-disconnecting set defines a submodular function. This implies that the set of all S inducing minim um-cost disconnecting sets is the set of closures of a binary relation , thus extending Picard-Queyranne's( 1980) result on ordinary minimum cuts. We apply this result to two-pair multicommodity problems in undi rected networks, extending Hu's (1963) result to disconnecting sets th at may include vertices as well as edges. These results and a result o f Provan and Shier(1994) may be used for generating all sets S that in duce such minimum-cost disconnecting sets and ranking such sets in ord er of corresponding costs, for both one-pair problems in mixed network s and two-pair problems in undirected networks. (C) 1996 John Wiley & Sons, Inc.