Ancestor tree for arbitrary multi-terminal-cut functions

Ancestor tree for arbitrary multi-terminal-cut functions

0.00 Avg rating0 Votes
Article ID: iaor19921111
Country: Switzerland
Volume: 33
Start Page Number: 199
End Page Number: 213
Publication Date: Nov 1991
Journal: Annals of Operations Research
Authors:
Abstract:

In many applications, a function is defined on the cuts of a network. In the max-flow min-cut theorem, the function on a cut is simply the sum of all capacities of edges across the cut, and what is wanted is the minimum value of a cut separating a given pair of nodes. To find the minimum cuts separating equ1pairs of nodes, it only needs equ2computations to construct the cut-tree. In general, arbitrary values associated with all cuts in a network can be defined, and assumed that there is a routine which gives the minimum cut separating a pair of nodes. To find the minimum cuts separating equ3pairs of nodes, it also only needs n-1 routine calls to construct a binary tree which gives all equ4minimum partitions. The binary tree is analogous to the cut-tree of Gomory and Hu.

Reviews

Required fields are marked *. Your email address will not be published.