A near-linear time algorithm for constructing a cactus representation of minimum cuts

MaRDI QIDQ4633832zbMATH OpenFDO

Authors Debmalya Panigrahi, David R. Karger

Publication date 6 May 2019

Full work available at URL https://dl.acm.org/citation.cfm?id=1496798

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Data structures (68P05)

Recommendations

• A fast algorithm for cactus representations of minimum cuts
• scientific article; zbMATH DE number 1187160
• Building Chain and Cactus Representations of All Minimum Cuts from Hao–Orlin in the Same Asymptotic Run Time
• CONSTRUCTING CACTUS REPRESENTATION FOR ALL MINIMUM CUTS IN AN UNDIRECTED NETWORK
• Deterministic global minimum cut of a simple graph in near-linear time

Cited in

(12)

• Compact cactus representations of all non-trivial min-cuts
• Building Chain and Cactus Representations of All Minimum Cuts from Hao–Orlin in the Same Asymptotic Run Time
• Canonical cactus representation for miminum cuts
• scientific article; zbMATH DE number 1263227 (Why is no real title available?)
• Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs
• scientific article; zbMATH DE number 1187160 (Why is no real title available?)
• A fast algorithm for cactus representations of minimum cuts
• A single exponential-time FPT algorithm for cactus contraction
• scientific article; zbMATH DE number 2086917 (Why is no real title available?)
• Minimum cuts and sparsification in hypergraphs
• Deformable Polygon Representation and Near-Mincuts
• On finding fundamental cut sets

This page was built for publication: A near-linear time algorithm for constructing a cactus representation of minimum cuts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4633832)