DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2016.7

Routing with Congestion in Acyclic Digraphs

Authors: Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, and Roman Rabinovich

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract

We study the version of the k-disjoint paths problem where k demand pairs (s_1,t_1), ..., (s_k,t_k) are specified in the input and the paths in the solution are allowed to intersect, but such that no vertex is on more than c paths. We show that on directed acyclic graphs the problem is solvable in time n^{O(d)} if we allow congestion k-d for k paths. Furthermore, we show that, under a suitable complexity theoretic assumption, the problem cannot be solved in time f(k)n^{o(d*log(d))} for any computable function f.

Cite as

Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, and Roman Rabinovich. Routing with Congestion in Acyclic Digraphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 7:1-7:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{amiri_et_al:LIPIcs.MFCS.2016.7,
  author =	{Amiri, Saeed Akhoondian and Kreutzer, Stephan and Marx, D\'{a}niel and Rabinovich, Roman},
  title =	{{Routing with Congestion in Acyclic Digraphs}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{7:1--7:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.7},
  URN =		{urn:nbn:de:0030-drops-64244},
  doi =		{10.4230/LIPIcs.MFCS.2016.7},
  annote =	{Keywords: algorithms, disjoint paths, congestion, acyclic digraphs, XP, W\lbrack1\rbrack-hard}
}

Search Results

Documents authored by Amiri, Saeed Akhoondian

Routing with Congestion in Acyclic Digraphs

Abstract

Cite as

Thanks for your feedback!

Could not send message