Back to Search
Start Over
COMPACT REPRESENTATIONS OF CUTS.
- Source :
- SIAM Journal on Discrete Mathematics; 2000, Vol. 14 Issue 1, p49-66, 18p
- Publication Year :
- 2000
-
Abstract
- Consider the <subscript>2</subscript><superscript>n</superscript> (or O(n²)) min-cut problems on a graph with n nodes and nonnegative edge weights. Gomory and Hu [J. Soc. Indust. Appl. Math., 9 (1961), pp. 551–570] showed (essentially) that there are at most n-1 different min-cuts. They also described a compact structure (the flow equivalent tree) of size O(n) with the following property: for any pair of nodes, the value of a min-cut can be obtained from this structure. Furthermore, they showed how this structure can be found by solving only n - 1 min-cut problems. This paper contains generalizations of these results. For example, consider a k-terminal cut problem on a graph: for a given set of k nodes, delete a minimum weight set of edges (called a k-cut) so that each of the k nodes is in a different component. There are <subscript>k</subscript><superscript>n</superscript> (or O(n<superscript>k</superscript>)) such problems. Hassin [Math. Oper. Res., 13 (1988), pp. 535–542] showed (essentially) that there are at most <subscript>k-1</subscript><superscript>n-1</superscript> (or O(n<superscript>k-1</superscript>)) different min k-cuts. We describe a compact structure of size O(n<superscript>k-1</superscript>) with the following property: for any k nodes, the value of a min k-cut can be obtained from this structure. We also show how this structure can be found by solving only <subscript>k-1</subscript><superscript>n-1</superscript> k-terminal cut problems. This work builds upon the results of Hassin [Math. Oper. Res., 13 (1988), pp. 535–542], [Oper. Res. Lett., 9 (1990), pp. 315–318], and [Lecture Notes in Comput. Sci. 450, 1990, pp. 228–299]. [ABSTRACT FROM AUTHOR]
- Subjects :
- TREE graphs
GRAPH theory
GRAPHIC methods
ALGORITHMS
MATHEMATICAL diagrams
MATHEMATICS
Subjects
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 14
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 13206903