ISSN:
1436-4646
Keywords:
Mathematics Subject Classification (1991): 05C65, 05C40, 90C27
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s101070050035
Permalink