
Accession Number : AD0750284
Title : Monotone Minimum NodeCuts 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 nodecut 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 nodecut is known for a particular network and another node is added to the network then it is shown that a minimum nodecut exists for the new network which either contains the former minimum nodecut or has the complement of the former minimum nodecut contained in its complement. When the network is acyclic and a particular node is added it is shown that a minimum nodecut in the original network will be contained in a minimum nodecut 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