Ancestor tree for arbitrary multi-terminal cut functions |
| |
Authors: | C K Cheng T C Hu |
| |
Institution: | (1) Department of Computer Science and Engineering, University of California, 92093 San Diego, La Jolla, CA, USA |
| |
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 we want the minimum value of a cut separating a given pair of nodes. To find the minimum cuts separating
pairs of nodes, we only needn – 1 computations to construct the cut-tree. In general, we can define arbitrary values associated with all cuts in a network, and assume that there is a routine which gives the minimum cut separating a pair of nodes. To find the minimum cuts separating
pairs of nodes, we also only needn – 1 routine calls to construct a binary tree which gives all
minimum partitions. The binary tree is analogous to the cut-tree of Gomory and Hu. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|