Computing maximum mean cuts

DOI10.1016/0166-218X(92)00188-RzbMath0824.90058OpenAlexW2007315239MaRDI QIDQ1329796

Thomas R. Ervolina, S. Thomas McCormick

Publication date: 31 July 1994

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(92)00188-r

zbMATH Keywords

directed networkmaximum mean cutstrongly polynomial minimum cost network flow algorithm

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10)

Related Items (11)

How to compute least infeasible flows ⋮ Fractional 0-1 programming: applications and algorithms ⋮ Complexity of source-sink monotone 2-parameter min cut ⋮ An \(O(mn \log (nU))\) time algorithm to solve the feasibility problem ⋮ A submodular optimization problem with side constraints ⋮ Algorithms for the minimum cost circulation problem based on maximizing the mean improvement ⋮ Two strongly polynomial cut cancelling algorithms for minimum cost network flow ⋮ Minimax inverse problems of minimum cuts ⋮ Structural and algorithmic properties for parametric minimum cuts ⋮ A new algorithm for solving the feasibility problem of a network flow ⋮ Approximate binary search algorithms for mean cuts and cycles

Uses Software

• DIMACS
• NETGEN

Cites Work

• Two strongly polynomial cut cancelling algorithms for minimum cost network flow
• Parametric shortest path algorithms with an application to cyclic staffing
• New scaling algorithms for the assignment and minimum mean cycle problems
• Algorithms for the minimum cost circulation problem based on maximizing the mean improvement
• A characterization of the minimum cycle mean in a digraph
• A faster parametric minimum-cut algorithm
• Approximate binary search algorithms for mean cuts and cycles
• On the \(\epsilon\)-perturbation method for avoiding degeneracy
• Finding minimum-cost circulations by canceling negative cycles
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• A new approach to the maximum-flow problem
• Improved Time Bounds for the Maximum Flow Problem
• Combinatorial Optimization with Rational Objective Functions
• The minimum cost flow problem: A unifying approach to dual algorithms and a new tree-search algorithm
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems
• Two-Processor Scheduling with Start-Times and Deadlines
• A Fast Parametric Maximum Flow Algorithm and Applications
• A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Computing maximum mean cuts