Accession Number:
AD0750284
Title:
Monotone Minimum Node-Cuts in Capacitated Networks,
Descriptive Note:
Corporate Author:
CALIFORNIA UNIV BERKELEY OPERATIONS RESEARCH CENTER
Personal Author(s):
Report Date:
1970-12-01
Pagination or Media Count:
23.0
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
Subject Categories:
- Operations Research