Minimal disconnecting sets in directed multi‐commodity networks
John J. Jarvis, John B. Tindall · Naval Research Logistics Quarterly · 1972
Abstract 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.