A fast algorithm for cactus representations of minimum cuts

DOI10.1007/BF03167346zbMath1306.90165OpenAlexW1988832992MaRDI QIDQ2258383

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

graph algorithmminimum cutmaximum flowundirected networkcactus representation

Mathematics Subject Classification ID

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

Related Items

Unnamed Item ⋮ Generating partitions of a graph into a fixed number of minimum weight cuts ⋮ Computing finest mincut partitions of a graph and application to routing problems ⋮ Graph connectivity and its augmentation: Applications of MA orderings ⋮ Phylogenetic graph models beyond trees ⋮ An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree

Cites Work

• Canonical cactus representation for miminum cuts
• A simplified \(\widetilde{O}(nm)\) time edge-splitting algorithm in undirected graphs
• Augmenting undirected connectivity in RNC and in randomized Õ(n³) time
• On the structure of all minimum cuts in a network and applications
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• A Fast Algorithm for Optimally Increasing the Edge Connectivity
• A simple min-cut algorithm
• An Analytical Solution of Vector Diffraction for Focusing Optical Systems
• Data Security Equals Graph Connectivity
• CONSTRUCTING CACTUS REPRESENTATION FOR ALL MINIMUM CUTS IN AN UNDIRECTED NETWORK
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item