✦ LIBER ✦
Building Chain and Cactus Representations of All Minimum Cuts from Hao–Orlin in the Same Asymptotic Run Time
✍ Scribed by Lisa Fleischer
- Publisher
- Elsevier Science
- Year
- 1999
- Tongue
- English
- Weight
- 214 KB
- Volume
- 33
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
A cactus is a simple data structure that represents all minimum cuts of a weighted, undirected graph in linear space. We describe the first algorithm that can build a cactus from the asymptotically fastest deterministic algorithm that finds all minimum cuts in a weighted graphᎏthe Hao᎐Orlin minimum cut algorithm. This improves the deterministic time to construct the cactus in graphs with n Ž 3 . Ž 2 . vertices and m edges from O n to O nm log n rm .