An efficient algorithm for the minimum capacity cut problem
From MaRDI portal
An algorithm to find a minimum cut in a network is presented. The complexity of this algorithm is \(O(n^ 4)\), the same as that given by \textit{R. E. Gomory} and \textit{T. C. Hu} [J. SIAM 9, 551-570 (1961; Zbl 0112.124)]. But, according to the author, this algorithm is easier to implement and empirically superior to the standard algorithm.
Recommendations
Cites work
- Generalized Feedback Shift Register Pseudorandom Number Algorithm
- scientific article; zbMATH DE number 3936534 (Why is no real title available?)
- Maximal Flow Through a Network
- Multi-Terminal Network Flows
- Optimization of a 532-city symmetric traveling salesman problem by branch and cut
- Selected Applications of Minimum Cuts in Networks
- Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
- Trees and Cuts
Cited in
(35)- The traveling purchaser problem with budget constraint
- Minimizing symmetric submodular functions
- A branch-and-cut algorithm for vehicle routing problems
- Minimum cut problem using bases of extended polymatroids
- Computational experience with a branch-and-cut algorithm for flowshop scheduling with setups.
- Cardinality constrained minimum cut problems: complexity and algorithms.
- Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems
- The traveling salesman problem with draft limits
- Implementing an efficient minimum capacity cut algorithm
- A branch-and-bound algorithm for the minimum cut linear arrangement problem
- On solving cycle problems with branch-and-cut: extending shrinking and exact subcycle elimination separation algorithms
- Models and algorithms for the traveling salesman problem with time-dependent service times
- Generating subtour elimination constraints for the TSP from pure integer solutions
- A distributed exact algorithm for the multiple resource constrained sequencing problem
- Exact solutions to linear programming problems
- A branch-and-cut-and-price algorithm for vertex-biconnectivity augmentation
- A branch-and-cut framework for the consistent traveling salesman problem
- Minimum Cuts of Simple Graphs in Almost Always Linear Time
- scientific article; zbMATH DE number 3900472 (Why is no real title available?)
- Simplifying maximum flow computations: the effect of shrinking and good initial flows
- A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
- Practical minimum cut algorithms
- TBGMax: leveraging two-boundary graph pattern for lossless maximum-flow acceleration
- Randomized contractions for multiobjective minimum cuts
- An optimal algorithm for the minimum edge cardinality cut surface problem
- Branch and cut methods for network optimization
- A matheuristic algorithm for the pollution and energy minimization traveling salesman problems
- Theoretical and computational analysis of a new formulation for the rural postman problem and the general routing problem
- Finding a second Hamiltonian decomposition of a 4-regular multigraph by integer linear programming
- Branch-and-cut algorithms for the traveling salesman problem with job times
- Graph connectivity and its augmentation: Applications of MA orderings
- A branch-and-cut algorithm for the minimum labeling Hamiltonian cycle problem and two variants
- A linear time algorithm for the maximum capacity path problem
- Solution of large-scale symmetric travelling salesman problems
- Facet identification for the symmetric traveling salesman polytope
This page was built for publication: An efficient algorithm for the minimum capacity cut problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q922927)
