A new?old algorithm for minimum-cut and maximum-flow in closure graphs

DOI10.1002/net.1012zbMath1044.90083OpenAlexW2169825170MaRDI QIDQ2744651

Dorit S. Hochbaum

Publication date: 30 July 2002

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.1012

zbMATH Keywords

sensitivity analysismaximum flowclosure graphLerchs-Grossmann algorithmminimum-cut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

The Parametric Closure Problem ⋮ THE LAYERED NET SURFACE PROBLEMS IN DISCRETE GEOMETRY AND MEDICAL IMAGE SEGMENTATION ⋮ Production phase and ultimate pit limit design under commodity price uncertainty ⋮ MineLib: a library of open pit mining problems ⋮ Enhanced instance space analysis for the maximum flow problem ⋮ Models and methods for solving the problem of network vulnerability ⋮ Solving the parametric bipartite maximum flow problem in unbalanced and closure bipartite graphs ⋮ A combinatorial algorithm for weighted stable sets in bipartite graphs ⋮ A stable marriage requires communication ⋮ EFFICIENT ALGORITHMS FOR THE OPTIMAL-RATIO REGION DETECTION PROBLEMS IN DISCRETE GEOMETRY WITH APPLICATIONS ⋮ Stackelberg Max Closure with Multiple Followers

Cites Work

• Unnamed Item
• A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time
• A theorem on flows in networks
• Unimodular functions
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• On implementing the push-relabel method for the maximum flow problem
• A data structure for dynamic trees
• A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem
• Fast Algorithms for Bipartite Network Flow
• Optimal attack and reinforcement of a network
• A new approach to the maximum-flow problem
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases
• Maximal Closure of a Graph and Applications to Combinatorial Problems
• A network simplex method
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• The Complexity of Multiterminal Cuts
• A Faster Deterministic Maximum Flow Algorithm
• Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
• A new approach to the minimum cut problem
• A simple min-cut algorithm
• A Fast Parametric Maximum Flow Algorithm and Applications
• Possible Winners in Partially Completed Tournaments
• A Selection Problem of Shared Fixed Costs and Network Flows
• Notes—On a Selection Problem

This page was built for publication: A new?old algorithm for minimum-cut and maximum-flow in closure graphs