A fast algorithm for the generalized parametric minimum cut problem and applications

DOI10.1007/BF01758775zbMath0763.90081MaRDI QIDQ1186785

Dan Gusfield, Charles U. Martel

Publication date: 28 June 1992

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

monotone parametric flow networksparametric minimum cutsequence of network flow computations

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (14)

Dynamic expression trees ⋮ On some large-scale LP relaxations for the graph partitioning problem and their optimal solutions ⋮ Complexity of source-sink monotone 2-parameter min cut ⋮ Optimal hierarchical clustering on a graph ⋮ Refining the complexity of the sports elimination problem ⋮ A connection between sports and matroids: how many teams can we beat? ⋮ Parametric stable marriage and minimum cuts ⋮ A note on the parametric maximum flow problem and some related reoptimization issues ⋮ Universally maximum flow with piecewise-constant capacities ⋮ Structural and algorithmic properties for parametric minimum cuts ⋮ EFFICIENT ALGORITHMS FOR THE OPTIMAL-RATIO REGION DETECTION PROBLEMS IN DISCRETE GEOMETRY WITH APPLICATIONS ⋮ Baseball playoff eliminations: An application of linear programming. Erratum ⋮ Complexity results for the \(p\)-median problem with mutual communication ⋮ A faster parametric minimum-cut algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Complexity of Counting Stable Marriages
• Effective algorithm for the weber problem with a rectangular metric
• Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases
• Critical Load Factors in Two-Processor Distributed Systems
• A Cut Approach to the Rectilinear Distance Facility Location Problem
• A Fast Parametric Maximum Flow Algorithm and Applications
• Possible Winners in Partially Completed Tournaments
• College Admissions and the Stability of Marriage

This page was built for publication: A fast algorithm for the generalized parametric minimum cut problem and applications