Abstract | ||
---|---|---|
The second problem we consider is to find a compact representation of F. We prove that there exists a so-called hypercactus
K of size O(|V|), consisting of cycles and (hyper)edges arranged in a tree-like manner, and a mapping from V to V(K) in such
a way that there is a bijection between the minimum cuts of K and the members of F. If F corresponds to the minimum cuts of
a k-edge-connected graph then K reduces to the well-known cactus representation of minimum cuts due to Dinitz et al.
|
Year | DOI | Venue |
---|---|---|
1999 | 10.1007/s101070050035 | Math. Program. |
Keywords | Field | DocType |
minimum cut,connected graph | Graph theory,Discrete mathematics,Graph,Combinatorics,Mathematical optimization,Bijection,Existential quantification,Combinatorial optimization,Connectivity,Mathematics | Journal |
Volume | Issue | ISSN |
84 | 3 | 1436-4646 |
Citations | PageRank | References |
2 | 0.42 | 2 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tamás Fleiner | 1 | 241 | 27.45 |
Tibor Jordán | 2 | 713 | 78.34 |