Implementing an efficient minimum capacity cut algorithm

DOI10.1007/BF01582226zbMath0821.90130OpenAlexW2042852020MaRDI QIDQ1804650

Tadashi Ono, Toshihide Ibaraki, Hiroshi Nagamochi

Publication date: 27 September 1995

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

polynomial algorithmundirected networkminimum capacity cut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10)

Related Items

Efficient algorithms for the problems of enumerating cuts by non-decreasing weights, An integer programming approach for the time-dependent traveling salesman problem with time windows, Minimum cut problem using bases of extended polymatroids, Unnamed Item, A note on the minimization of symmetric and general submodular functions, Generating partitions of a graph into a fixed number of minimum weight cuts, Facets from gadgets, Practical Minimum Cut Algorithms, Speeding up the Gomory-Hu parallel cut tree algorithm with efficient graph contractions, Exploiting planarity in separation routines for the symmetric traveling salesman problem, Graph connectivity and its augmentation: Applications of MA orderings, Minimum Cuts of Simple Graphs in Almost Always Linear Time, Minimizing symmetric submodular functions, A fast algorithm for minimum weight odd circuits and cuts in planar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• An efficient algorithm for the minimum capacity cut problem
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• A new approach to the maximum-flow problem
• Multi-Terminal Network Flows
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• On sparse subgraphs preserving connectivity properties
• An Õ(n²) algorithm for minimum cuts