Maximum edge-disjoint paths in planar graphs with congestion 2

DOI10.1007/S10107-020-01513-1zbMath1470.90107OpenAlexW3028209208MaRDI QIDQ2039241

Loïc Séguin-Charbonneau, F. Bruce Shepherd

Publication date: 2 July 2021

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

Full work available at URL: https://doi.org/10.1007/s10107-020-01513-1

zbMATH Keywords

flowsedge-disjoint pathsintegrality gap

Mathematics Subject Classification ID

Linear programming (90C05) Combinatorial optimization (90C27)

Related Items (1)

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• On the single-source unsplittable flow problem
• Multicommodity flows in planar graphs
• Edge-disjoint paths in Planar graphs with constant congestion
• (Almost) Tight bounds and existence theorems for single-commodity confluent flows
• Degree-constrained network flows
• All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs
• New hardness results for routing on disjoint paths
• Maximum Edge-Disjoint Paths in k-Sums of Graphs
• Routing in undirected graphs with constant congestion
• Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems

This page was built for publication: Maximum edge-disjoint paths in planar graphs with congestion 2