文章基本信息

标题：Routing Symmetric Demands in Directed Minor-Free Graphs with Constant Congestion
本地全文：下载
作者：Timothy Carpenter ; Ario Salmasi ; Anastasios Sidiropoulos 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：145
页码：1-15
DOI：10.4230/LIPIcs.APPROX-RANDOM.2019.14
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Routing; Node-disjoint; Symmetric demands; Minor-free graphs