A new saling algorithm for the maximum mean cut problem

DOI10.1007/BF01240735zbMath0793.68116OpenAlexW2090219729MaRDI QIDQ1317477

Satoru Fujishige, Shinji Misono, Shu Tezuka, Kazuo Iwano

Publication date: 17 April 1994

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01240735

zbMATH Keywords

binary searchscaling algorithmcirculation feasibilitymaximum meanminimum-cost circulation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (8)

Fractional 0-1 programming and submodularity ⋮ How to compute least infeasible flows ⋮ Fractional 0-1 programming: applications and algorithms ⋮ A Fast Approximation Algorithm For The Subset-Sum Problem ⋮ The quickest flow problem ⋮ Minimax inverse problems of minimum cuts ⋮ Tight bounds on the number of minimum-mean cycle cancellations and related results ⋮ Approximate binary search algorithms for mean cuts and cycles

Cites Work

• A linear time randomizing algorithm for searching ranked functions
• New scaling algorithms for the assignment and minimum mean cycle problems
• A characterization of the minimum cycle mean in a digraph
• A Fast and Simple Algorithm for the Maximum Flow Problem
• Finding minimum-cost circulations by canceling negative cycles
• A new approach to the maximum-flow problem
• Improved Time Bounds for the Maximum Flow Problem
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• A Fast Algorithm for Optimally Increasing the Edge Connectivity
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A new saling algorithm for the maximum mean cut problem