Accession Number:

AD0750284

Title:

Monotone Minimum Node-Cuts in Capacitated Networks,

Descriptive Note:

Corporate Author:

CALIFORNIA UNIV BERKELEY OPERATIONS RESEARCH CENTER

Personal Author(s):

• Topkis,Donald M.

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

Descriptors:

• (*GRAPHICS
• ALGORITHMS)
• NETWORKS
• MATHEMATICAL MODELS
• SET THEORY
• THEOREMS
• OPTIMIZATION

Subject Categories:

• Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE