A strongly polynomial parametric algorithm for computing a maximum mean cut in a directed network is discussed. It needs at most \(O(n)\) min cut calculations. This algorithm provides the missing component in a strongly polynomial minimum cost network flow algorithm based on cancelling maximum mean cuts developed by the authors earlier. Several other algorithms for computing maximum mean cuts are reviewed.
Recommendations
Cites work
- A characterization of the minimum cycle mean in a digraph
- A Fast Parametric Maximum Flow Algorithm and Applications
- A faster parametric minimum-cut algorithm
- A new approach to the maximum-flow problem
- A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems
- Algorithms for the minimum cost circulation problem based on maximizing the mean improvement
- Applying Parallel Computation Algorithms in the Design of Serial Algorithms
- Approximate binary search algorithms for mean cuts and cycles
- Combinatorial Optimization with Rational Objective Functions
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- Finding minimum-cost circulations by canceling negative cycles
- scientific article; zbMATH DE number 3121287 (Why is no real title available?)
- scientific article; zbMATH DE number 3156381 (Why is no real title available?)
- scientific article; zbMATH DE number 193993 (Why is no real title available?)
- scientific article; zbMATH DE number 1256704 (Why is no real title available?)
- scientific article; zbMATH DE number 515931 (Why is no real title available?)
- scientific article; zbMATH DE number 742963 (Why is no real title available?)
- scientific article; zbMATH DE number 3302125 (Why is no real title available?)
- scientific article; zbMATH DE number 3197631 (Why is no real title available?)
- Improved Time Bounds for the Maximum Flow Problem
- NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems
- New scaling algorithms for the assignment and minimum mean cycle problems
- On the \(\epsilon\)-perturbation method for avoiding degeneracy
- Parametric shortest path algorithms with an application to cyclic staffing
- The minimum cost flow problem: A unifying approach to dual algorithms and a new tree-search algorithm
- Two strongly polynomial cut cancelling algorithms for minimum cost network flow
- Two-Processor Scheduling with Start-Times and Deadlines
Cited in
(14)- Algorithms for the minimum cost circulation problem based on maximizing the mean improvement
- A new saling algorithm for the maximum mean cut problem
- Approximate binary search algorithms for mean cuts and cycles
- How to compute least infeasible flows
- Fractional 0-1 programming: applications and algorithms
- Complexity of source-sink monotone 2-parameter min cut
- Minimax inverse problems of minimum cuts
- Online Maximum Directed Cut
- A submodular optimization problem with side constraints
- An \(O(mn \log (nU))\) time algorithm to solve the feasibility problem
- Two strongly polynomial cut cancelling algorithms for minimum cost network flow
- A survey of exact and approximation algorithms for linear-parametric optimization problems
- Structural and algorithmic properties for parametric minimum cuts
- A new algorithm for solving the feasibility problem of a network flow
This page was built for publication: Computing maximum mean cuts
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1329796)
