Multicommodity Disconnecting Set Problem
Y.P. Aneja, Ke Xiao · 2007
AbstractGiven a directed network G = (V, A) with positive capacity for each a Î A, and a specified set of source-sink pairs of vertices, the objective is to remove a set of arcs with minimum capacity so that the resulting network stops all communication from sources to their respective sinks. We study the facial structure of the polytope associated with the solutions of this problem and identify a general class of facets. We develop two algorithms: a simple cutting plane algorithm and a branch-and-cut algorithm for this problem and present computational results.