A faster parametric minimum-cut algorithm

DOI10.1007/BF01240737zbMath0795.68099OpenAlexW2020870396MaRDI QIDQ1317480

Dan Gusfield, Éva Tardos

Publication date: 11 September 1994

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

graph algorithmsnetwork flowlayoutcutsparametric cuts

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Directed graphs (digraphs), tournaments (05C20)

Related Items (5)

Computing maximum mean cuts ⋮ Optimal hierarchical clustering on a graph ⋮ Structural and algorithmic properties for parametric minimum cuts ⋮ Complexity results for the \(p\)-median problem with mutual communication ⋮ The least element property of center location on tree networks with applications to distance and precedence constrained problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parametric stable marriage and minimum cuts
• A fast algorithm for the generalized parametric minimum cut problem and applications
• Analysis of Preflow Push Algorithms for Maximum Network Flow
• A new approach to the maximum-flow problem
• A comparison of phase and nonphase network flow algorithms
• Effective algorithm for the weber problem with a rectangular metric
• Multifacility Location Problem with Rectilinear Distance by the Minimum-Cut Approach
• Computing the Strength of a Graph
• A Cut Approach to the Rectilinear Distance Facility Location Problem
• A Fast Parametric Maximum Flow Algorithm and Applications

This page was built for publication: A faster parametric minimum-cut algorithm