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

zbMATH Open1423.68346MaRDI QIDQ4633832FDOQ4633832

Authors: Debmalya Panigrahi, David R. Karger 

Publication date: 6 May 2019

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

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

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)

Cited In (12)

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

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)