Poly-logarithmic approximation for maximum node disjoint paths with constant congestion

DOI10.1137/1.9781611973105.24MaRDI QIDQ5741732zbMATH OpenOpenAlexFDO

Authors Chandra Chekuri, Alina Ene

Publication date 15 May 2019

Published in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973105.24

Mathematics Subject Classification ID

Flows in graphs (05C21) Paths and cycles (05C38) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Recommendations

• A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
• Improved approximation for node-disjoint paths in planar graphs
• An Improved Approximation Algorithm for the Edge-Disjoint Paths Problem with Congestion Two
• Breaking \(o(n^{1/2})\)-approximation algorithms for the edge-disjoint paths problem with congestion two
• On approximating node-disjoint paths in grids

Cited in

(11)

• New algorithms for maximum disjoint paths based on tree-likeness
• Routing with congestion in acyclic digraphs
• Routing in undirected graphs with constant congestion
• A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
• Shortest node-disjoint paths on random graphs
• New hardness results for routing on disjoint paths
• Constant congestion routing of symmetric demands in planar directed graphs
• Improved approximation for node-disjoint paths in grids with sources on the boundary
• Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators
• Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators
• The all-or-nothing flow problem in directed graphs with symmetric demand pairs

This page was built for publication: Poly-logarithmic approximation for maximum node disjoint paths with constant congestion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5741732)