Accession Number : AD0750284

Title :   Monotone Minimum Node-Cuts in Capacitated Networks,

Corporate Author : CALIFORNIA UNIV BERKELEY OPERATIONS RESEARCH CENTER

Personal Author(s) : Topkis,Donald M.

Report Date : DEC 1970

Pagination or Media Count : 23

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)

Descriptors :   (*GRAPHICS, ALGORITHMS), NETWORKS, MATHEMATICAL MODELS, SET THEORY, THEOREMS, OPTIMIZATION

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE