Canonical cactus representation for miminum cuts (Q1343494)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Canonical cactus representation for miminum cuts |
scientific article |
Statements
Canonical cactus representation for miminum cuts (English)
0 references
19 January 1995
0 references
It is known that all minimum cuts in a network \(N\) can be embedded in a cactus whose size is bounded by a linear function of the number of vertices in \(N\). However, such a representation is not unique. In this paper, the authors have introduced two canonical forms of a cactus representation named the `cycle-type' and `junction-type' and have shown their uniqueness. It is also shown that these cacti contain at most twice as many vertices as \(N\). Such a unique representation is helpful in designing an efficient algorithm for constructing a cactus representation for all the minimum cuts of a given network.
0 references
multigraph
0 references
canonical form
0 references
isomorphism
0 references
minimum cuts
0 references
cactus representation
0 references
algorithm
0 references
network
0 references
0 references