Monotone Minimum Node-Cuts in Capacitated Networks,
Abstract
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1970
- Accession Number
- AD0750284
Entities
People
- Donald M. Topkis
Organizations
- University of California, Berkeley