Monotone Minimum Node-Cuts in Capacitated Networks

摘要

The problem of finding a minimum node-cut in a capacitated network is shown to be a special case of the problem of minimizing a subadditive function over a lattice, and the theory developed by Topkis and Veinott relating to the latter problem is applied. If a minimum node-cut is known for a particular network and another node is added to the network then it is shown that a minimum node-cut exists for the new network which either contains the former minimum node-cut or has the complement of the former minimum node-cut contained in its complement. When the network is acyclic and a particular node is added it is shown that a minimum node-cut in the original network will be contained in a minimum node-cut in the new one. (Author)