2026-07-26T03:15:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11229 2024-03-06T10:47:45Z ddc:004 open_access

Routing Symmetric Demands in Directed Minor-Free Graphs with Constant Congestion Carpenter, Timothy Salmasi, Ario Sidiropoulos, Anastasios Routing Node-disjoint Symmetric demands Minor-free graphs The problem of routing in graphs using node-disjoint paths has received a lot of attention and a polylogarithmic approximation algorithm with constant congestion is known for undirected graphs [Chuzhoy and Li 2016] and [Chekuri and Ene 2013]. However, the problem is hard to approximate within polynomial factors on directed graphs, for any constant congestion [Chuzhoy, Kim and Li 2016]. Recently, [Chekuri, Ene and Pilipczuk 2016] have obtained a polylogarithmic approximation with constant congestion on directed planar graphs, for the special case of symmetric demands. We extend their result by obtaining a polylogarithmic approximation with constant congestion on arbitrary directed minor-free graphs, for the case of symmetric demands. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Timothy Carpenter and Ario Salmasi and Anastasios Sidiropoulos 2019 Is Part Of LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2019.14 urn:nbn:de:0030-drops-112290 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.14 eng https://creativecommons.org/licenses/by/3.0/legalcode