Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators
From MaRDI portal
Publication:5918431
DOI10.1007/978-3-030-73879-2_23zbMath1482.90232arXiv2007.10537OpenAlexW3160226286MaRDI QIDQ5918431
Bruce Shepherd, Guyslain Naves, Henry Xia
Publication date: 21 December 2021
Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2007.10537
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)
Related Items (1)
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
- An Approximation Algorithm for Fully Planar Edge-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
- Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2
- 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
- Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators
This page was built for publication: Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators
