Implementing an efficient minimum capacity cut algorithm

DOI10.1007/BF01582226MaRDI QIDQ1804650zbMATH OpenOpenAlexFDO

Authors Hiroshi Nagamochi, Tadashi Ono, Toshihide Ibaraki

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) Deterministic network models in operations research (90B10) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• An efficient algorithm for the minimum capacity cut problem
• Efficient algorithms for minimum range cut problems
• Practical performance of efficient minimum cut algorithms
• scientific article; zbMATH DE number 177540
• Practical minimum cut algorithms
• Practical minimum cut algorithms
• A simple and fast min-cut algorithm
• Fundamentals of Computation Theory
• scientific article; zbMATH DE number 7759280
• scientific article; zbMATH DE number 1256719

Cites work

• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 742961 (Why is no real title available?)
• 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
• An Õ(n²) algorithm for minimum cuts
• An efficient algorithm for the minimum capacity cut problem
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Multi-Terminal Network Flows
• On sparse subgraphs preserving connectivity properties

Cited in

(20)

• Speeding up the Gomory-Hu parallel cut tree algorithm with efficient graph contractions
• Practical minimum cut algorithms
• Minimum cut problem using bases of extended polymatroids
• Facets from gadgets
• Efficient algorithms for the problems of enumerating cuts by non-decreasing weights
• scientific article; zbMATH DE number 742961 (Why is no real title available?)
• A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
• Minimum Cuts of Simple Graphs in Almost Always Linear Time
• Generating partitions of a graph into a fixed number of minimum weight cuts
• Minimizing symmetric submodular functions
• Practical performance of efficient minimum cut algorithms
• An integer programming approach for the time-dependent traveling salesman problem with time windows
• Graph connectivity and its augmentation: Applications of MA orderings
• An efficient algorithm for the minimum capacity cut problem
• scientific article; zbMATH DE number 7651198 (Why is no real title available?)
• Rapidly computing robust minimum capacity s-t cuts: a case study in solving a sequence of maximum flow problems
• Exploiting planarity in separation routines for the symmetric traveling salesman problem
• A fast algorithm for minimum weight odd circuits and cuts in planar graphs
• A note on the minimization of symmetric and general submodular functions
• Theoretical and computational analysis of a new formulation for the rural postman problem and the general routing problem

This page was built for publication: Implementing an efficient minimum capacity cut algorithm

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