A fast algorithm for cactus representations of minimum cuts

DOI10.1007/BF03167346MaRDI QIDQ2258383zbMATH OpenOpenAlexFDO

Authors Hiroshi Nagamochi, Yoshitaka Nakao, Toshihide Ibaraki

Publication date 3 March 2015

Published in Japan Journal of Industrial and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf03167346

zbMATH Keywords

cactus representationgraph algorithmmaximum flowminimum cutundirected network

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Programming involving graphs or networks (90C35)

Recommendations

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

Cites work

• A Fast Algorithm for Optimally Increasing the Edge Connectivity
• A simple min-cut algorithm
• A simplified \(\widetilde{O}(nm)\) time edge-splitting algorithm in undirected graphs
• An Analytical Solution of Vector Diffraction for Focusing Optical Systems
• Augmenting undirected connectivity in RNC and in randomized \(\tilde{O}(n^3)\) time
• Canonical cactus representation for miminum cuts
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• CONSTRUCTING CACTUS REPRESENTATION FOR ALL MINIMUM CUTS IN AN UNDIRECTED NETWORK
• Data Security Equals Graph Connectivity
• scientific article; zbMATH DE number 437545 (Why is no real title available?)
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 1187160 (Why is no real title available?)
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 177555 (Why is no real title available?)
• On the structure of all minimum cuts in a network and applications

Cited in

(17)

• Phylogenetic graph models beyond trees
• Canonical cactus representation for miminum cuts
• An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
• Generating partitions of a graph into a fixed number of minimum weight cuts
• Compact cactus representations of all non-trivial min-cuts
• Computing finest mincut partitions of a graph and application to routing problems
• A single exponential-time FPT algorithm for cactus contraction
• Deformable Polygon Representation and Near-Mincuts
• scientific article; zbMATH DE number 1187160 (Why is no real title available?)
• scientific article; zbMATH DE number 1263227 (Why is no real title available?)
• A near-linear time algorithm for constructing a cactus representation of minimum cuts
• scientific article; zbMATH DE number 2086917 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 7651198 (Why is no real title available?)
• Applying a cut-based data reduction rule for weighted cluster editing in polynomial time
• Graph connectivity and its augmentation: Applications of MA orderings

This page was built for publication: A fast algorithm for cactus representations of minimum cuts

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