corc logo

Abstract of CORC technical report TR-98-01:

Building chain and cactus representations of all minimum cuts from Hao-Orlin in the same asymptotic run time

Lisa Fleischer, 1998

A cactus tree is a simple data structure that represents all minimum cuts of a weighted graph in linear space. We describe the first algorithm that can build a cactus tree from the asymptotically fastest deterministic algorithm that finds all minimum cuts in a weighted graph -- the Hao-Orlin minimum cut algorithm. This improves the time to construct the cactus in graphs with n vertices and m edges from O() to O(nm log n²/m).