Structural and algorithmic properties for parametric minimum cuts
From MaRDI portal
Publication:715078
DOI10.1007/s10107-011-0463-1zbMath1269.90126OpenAlexW1999966159MaRDI QIDQ715078
S. Thomas McCormick, Fabio Tardella, Frieda Granot, Maurice Queyranne
Publication date: 15 October 2012
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-011-0463-1
Programming involving graphs or networks (90C35) Sensitivity, stability, parametric optimization (90C31)
Related Items
A Fluid Model for One-Sided Bipartite Matching Queues with Match-Dependent Rewards, Parametric Computation of Minimum-Cost Flows with Piecewise Quadratic Costs, Complexity of source-sink monotone 2-parameter min cut, Maximum flows in parametric graph templates, A stronger lower bound on parametric minimum spanning trees, Lattice flows in networks, A Polynomial Algorithm for a Class of 0–1 Fractional Programming Problems Involving Composite Functions, with an Application to Additive Clustering
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A simple version of Karzanov's blocking flow algorithm
- A fast algorithm for the generalized parametric minimum cut problem and applications
- Generalization of a theorem on the parametric maximum flow problem
- A faster parametric minimum-cut algorithm
- Computing maximum mean cuts
- A push-relabel framework for submodular function minimization and applications to parametric optimization
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- A note on the parametric maximum flow problem and some related reoptimization issues
- Ordered optimal solutions and parametric minimum cut problems
- Universally maximum flow with piecewise-constant capacities
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- The Pseudoflow Algorithm: A New Algorithm for the Maximum-Flow Problem
- Complexity of some parametric integer and network programming problems
- Minimum-delay routing in continuous-time dynamic networks with Piecewise-constant capacities
- A new approach to the maximum-flow problem
- A comparison of phase and nonphase network flow algorithms
- Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector
- Selected Applications of Minimum Cuts in Networks
- Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases
- Critical Load Factors in Two-Processor Distributed Systems
- Minimizing a Submodular Function on a Lattice
- Monotone Comparative Statics
- Improved Algorithms for Bipartite Network Flow
- A Faster Deterministic Maximum Flow Algorithm
- A Fast Parametric Maximum Flow Algorithm and Applications
- Fast Algorithms for Parametric Scheduling Come From Extensions to Parametric Maximum Flow
- A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization
- On Convex Minimization over Base Polytopes
- Algorithms – ESA 2005
- On Nonlinear Fractional Programming
- A Selection Problem of Shared Fixed Costs and Network Flows
- On network flow functions
