License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.14
URN: urn:nbn:de:0030-drops-112290
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11229/
Go to the corresponding LIPIcs Volume Portal

Carpenter, Timothy ; Salmasi, Ario ; Sidiropoulos, Anastasios

Routing Symmetric Demands in Directed Minor-Free Graphs with Constant Congestion

pdf-format:
LIPIcs-APPROX-RANDOM-2019-14.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{carpenter_et_al:LIPIcs:2019:11229,
  author =	{Timothy Carpenter and Ario Salmasi and Anastasios Sidiropoulos},
  title =	{{Routing Symmetric Demands in Directed Minor-Free Graphs with Constant Congestion}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{14:1--14:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11229},
  URN =		{urn:nbn:de:0030-drops-112290},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.14},
  annote =	{Keywords: Routing, Node-disjoint, Symmetric demands, Minor-free graphs}
}

Keywords: Routing, Node-disjoint, Symmetric demands, Minor-free graphs
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Issue Date: 2019
Date of publication: 17.09.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI