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

DOI10.1002/NET.1012MaRDI QIDQ2744651zbMATH OpenOpenAlexFDO

Authors 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

closure graphLerchs-Grossmann algorithmmaximum flowminimum-cutsensitivity analysis

Mathematics Subject Classification ID

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

Review text

Closure graphs form a special subclass of digraphs; they include a source and sink in which only source adjacent arcs and sink adjacent arcs have finite capacities. The paper presents an algorithm for solving the minimum-cut problem on this class of digraphs based on the Lerchs-Grossmann algorithms without using the concept of a flow.

Recommendations

• A New Algorithm for Computing the Maximal Closure of a Graph
• scientific article; zbMATH DE number 742961
• Minimum cut problem using bases of extended polymatroids
• A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
• Minimum flows in directed s-t planar networks

Cites work

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

Cited in

(13)

• A new variant of the \(A^*\)-algorithm which closes a node at most once.
• Maximal closure on a graph with resource constraints
• Models and methods for solving the problem of network vulnerability
• Enhanced instance space analysis for the maximum flow problem
• A stable marriage requires communication
• A combinatorial algorithm for weighted stable sets in bipartite graphs
• Production phase and ultimate pit limit design under commodity price uncertainty
• A New Algorithm for Computing the Maximal Closure of a Graph
• MineLib: a library of open pit mining problems
• EFFICIENT ALGORITHMS FOR THE OPTIMAL-RATIO REGION DETECTION PROBLEMS IN DISCRETE GEOMETRY WITH APPLICATIONS
• Solving the parametric bipartite maximum flow problem in unbalanced and closure bipartite graphs
• THE LAYERED NET SURFACE PROBLEMS IN DISCRETE GEOMETRY AND MEDICAL IMAGE SEGMENTATION
• Stackelberg Max Closure with Multiple Followers

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2744651)