Canonical cactus representation for miminum cuts

DOI10.1007/BF03167227zbMath0814.05067OpenAlexW1985883567MaRDI QIDQ1343494

Hiroshi Nagamochi, Tiko Kameda

Publication date: 19 January 1995

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

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

zbMATH Keywords

networkmultigraphalgorithmisomorphismcanonical formminimum cutscactus representation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items

Unnamed Item, 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 fast algorithm for cactus representations of minimum cuts, Characterizing the flow equivalent trees of a network, Phylogenetic graph models beyond trees

Cites Work

• Unnamed Item
• A linear time algorithm for computing 3-edge-connected components in a multigraph
• \(A\,V^ 2\) algorithm for determining isomorphism of planar graphs
• Efficient algorithm for finding all minimal edge cuts of a nonoriented graph
• Calculating bounds on reachability and connectedness in stochastic networks
• Counting the number of minimum cuts in undirected multigraphs
• The Minimum Number of Edges and Vertices in a Graph with Edge Connectivity n and m n‐Bonds
• A Fast Algorithm for Optimally Increasing the Edge Connectivity
• CONSTRUCTING CACTUS REPRESENTATION FOR ALL MINIMUM CUTS IN AN UNDIRECTED NETWORK