Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation

DOI10.1007/s10107-010-0366-6zbMath1198.90072MaRDI QIDQ2638376

S. Thomas McCormick, Ali Ridha Mahjoub

Publication date: 16 September 2010

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-010-0366-6

Mathematics Subject Classification ID

90B18: Communication networks in operations research

90C59: Approximation methods and heuristics in mathematical programming

90B10: Deterministic network models in operations research

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on hop-constrained walk polytopes.
• Geometric algorithms and combinatorial optimization
• Mengerian theorems for paths of bounded length
• Multicommodity network flow with jump constraints
• On the directed hop-constrained shortest path problem
• On the complexity of vertex-disjoint length-restricted path problems
• On line disjoint paths of bounded length
• Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut
• A 2-path approach for odd-diameter-constrained minimum spanning and Steiner trees
• Maximal Flow Through a Network
• The two-edge connected hop-constrained network design problem: Valid inequalities and branch-and-cut
• Integer programming formulations for the two 4-hop-constrained paths problem
• Polyhedral Characterization of Discrete Dynamic Programming
• Length-Bounded Cuts and Flows
• A counterexample to a conjecture on paths of bounded length
• A generalization of max flow—min cut
• Two Edge-Disjoint Hop-Constrained Paths and Polyhedra
• The complexity of finding maximum disjoint paths with length constraints
• Network flow models for designing diameter‐constrained minimum‐spanning and Steiner trees
• Quickest Flows Over Time
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems