Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators

DOI10.1007/s10107-022-01780-0OpenAlexW3045332431MaRDI QIDQ5925650

Henry Xia, F. Bruce Shepherd, Guyslain Naves

Publication date: 14 March 2023

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

Full work available at URL: https://doi.org/10.1007/s10107-022-01780-0

Mathematics Subject Classification ID

Integer programming (90C10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Cuts, trees and \(\ell_1\)-embeddings of graphs
• Edge-disjoint paths in planar graphs
• Multicommodity flows in planar graphs
• Matroids and multicommodity flows
• Approximations for the disjoint paths problem in high-diameter planar networks
• Lower bounds on the distortion of embedding finite metric spaces in graphs
• The All-or-Nothing Multicommodity Flow Problem
• Improved Guarantees for Tree Cut Sparsifiers
• Multicommodity demand flow in a tree and packing integer programs
• The all-or-nothing multicommodity flow problem
• Lower-Stretch Spanning Trees
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs
• New hardness results for routing on disjoint paths
• Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation
• Edge-Disjoint Paths in Planar Graphs with Constant Congestion
• Maximum Edge-Disjoint Paths in k-Sums of Graphs
• Poly-logarithmic Approximation for Maximum Node Disjoint Paths with Constant Congestion
• Vertex Sparsifiers: New Results from Old Techniques
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems

This page was built for publication: Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators