Compact cactus representations of all non-trivial min-cuts

DOI10.1016/j.dam.2020.03.046zbMath1472.05085arXiv1810.03865OpenAlexW3015233796WikidataQ109517115 ScholiaQ109517115MaRDI QIDQ1983141

On-Hei S. Lo, Mikkel Thorup, Jens M. Schmidt

Publication date: 15 September 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1810.03865

zbMATH Keywords

cactus representationcontraction-based sparsificationDAG representationmin-cuts enumerationnon-trivial min-cuts

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Abstract computational complexity for mathematical programming problems (90C60) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (2)

Generalized cut trees for edge-connectivity ⋮ Unnamed Item

Cites Work

• Unnamed Item
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Extracting maximal information about sets of minimum cuts
• Canonical cactus representation for miminum cuts
• A matroid approach to finding edge connectivity and packing arborescences
• Multi-Terminal Network Flows
• Local Flow Partitioning for Faster Edge Connectivity
• Deterministic Edge Connectivity in Near-Linear Time

This page was built for publication: Compact cactus representations of all non-trivial min-cuts