Implementing an efficient minimum capacity cut algorithm

DOI10.1007/BF01582226zbMath0821.90130MaRDI QIDQ1804650

Toshihide Ibaraki, Hiroshi Nagamochi, Tadashi Ono

Publication date: 27 September 1995

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

zbMATH Keywords

polynomial algorithm; undirected network; minimum capacity cut

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C60: Abstract computational complexity for mathematical programming problems

90B10: Deterministic network models in operations research

Related Items

Graph connectivity and its augmentation: Applications of MA orderings, A fast algorithm for minimum weight odd circuits and cuts in planar graphs, Exploiting planarity in separation routines for the symmetric traveling salesman problem, Minimizing symmetric submodular functions, Minimum cut problem using bases of extended polymatroids, A note on the minimization of symmetric and general submodular functions, Minimum Cuts of Simple Graphs in Almost Always Linear Time

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