Minimal disconnecting sets in directed multi-commodity networks

The problem of finding minimal disconnecting sets for multi-commodity directed networks may be solved using an arc-path formulation and Gomory's all-integer integer programming algorithm. However, the number of network constraints may be astronomical for even moderately sized networks. This paper develops a finite algorithm similar to Gomory's, but requiring no more than m rows in the tableau, where m is the number of arcs in the network.