Building Chain and Cactus Representations of All Minimum Cuts from Hao–Orlin in the Same Asymptotic Run Time
From MaRDI portal
Publication:4939605
DOI10.1006/jagm.1999.1039zbMath0937.68154OpenAlexW2005075461MaRDI QIDQ4939605
Publication date: 28 May 2000
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jagm.1999.1039
Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)
Related Items (16)
How to draw the minimum cuts of a planar graph ⋮ Efficient algorithms for the problems of enumerating cuts by non-decreasing weights ⋮ Enumeration of labeled connected graphs with given order and size ⋮ Minimum Cuts and Sparsification in Hypergraphs ⋮ Spanning cactus: complexity and extensions ⋮ Approximation algorithms for flexible graph connectivity ⋮ Efficient Algorithms for the k Smallest Cuts Enumeration ⋮ Generating partitions of a graph into a fixed number of minimum weight cuts ⋮ A linear algorithm for the Hamiltonian completion number of the line graph of a cactus. ⋮ Computing finest mincut partitions of a graph and application to routing problems ⋮ Most balanced minimum cuts ⋮ Computing compatible tours for the symmetric traveling salesman problem ⋮ Complexity of the directed spanning cactus problem ⋮ Characterizing the flow equivalent trees of a network ⋮ Phylogenetic graph models beyond trees ⋮ Approximate spanning cactus
This page was built for publication: Building Chain and Cactus Representations of All Minimum Cuts from Hao–Orlin in the Same Asymptotic Run Time
