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

DOI10.1007/S10107-010-0366-6zbMath1198.90072OpenAlexW2171565779MaRDI QIDQ2638376

Ali Ridha Mahjoub, S. Thomas McCormick

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

Communication networks in operations research (90B18) Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10)

Related Items (11)

Length-bounded cuts: proper interval graphs and structural parameters ⋮ An extended network interdiction problem for optimal toll control ⋮ Edge degeneracy: algorithmic and structural results ⋮ On Polynomial-Time Combinatorial Algorithms for Maximum $L$-Bounded Flow ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems ⋮ A Flexible, Natural Formulation for the Network Design Problem with Vulnerability Constraints ⋮ On Algorithms Employing Treewidth for $L$-bounded Cut Problems ⋮ Margin of victory for tournament solutions ⋮ Complexity and algorithms for constant diameter augmentation problems

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

This page was built for publication: Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation