DROPS

Document

DOI: 10.4230/LIPIcs.SWAT.2016.15

On Routing Disjoint Paths in Bounded Treewidth Graphs

Authors: Alina Ene, Matthias Mnich, Marcin Pilipczuk, and Andrej Risteski

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract

We study the problem of routing on disjoint paths in bounded treewidth graphs with both edge and node capacities. The input consists of a capacitated graph G and a collection of k source-destination pairs M = (s_1, t_1), ..., (s_k, t_k). The goal is to maximize the number of pairs that can be routed subject to the capacities in the graph. A routing of a subset M' of the pairs is a collection P of paths such that, for each pair (s_i, t_i) in M', there is a path in P connecting s_i to t_i. In the Maximum Edge Disjoint Paths (MaxEDP) problem, the graph G has capacities cap(e) on the edges and a routing P is feasible if each edge e is in at most cap(e) of the paths of P. The Maximum Node Disjoint Paths (MaxNDP) problem is the node-capacitated counterpart of MaxEDP. In this paper we obtain an O(r^3) approximation for MaxEDP on graphs of treewidth at most r and a matching approximation for MaxNDP on graphs of pathwidth at most r. Our results build on and significantly improve the work by Chekuri et al. [ICALP 2013] who obtained an O(r * 3^r) approximation for MaxEDP.

Cite as

Alina Ene, Matthias Mnich, Marcin Pilipczuk, and Andrej Risteski. On Routing Disjoint Paths in Bounded Treewidth Graphs. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{ene_et_al:LIPIcs.SWAT.2016.15,
  author =	{Ene, Alina and Mnich, Matthias and Pilipczuk, Marcin and Risteski, Andrej},
  title =	{{On Routing Disjoint Paths in Bounded Treewidth Graphs}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.15},
  URN =		{urn:nbn:de:0030-drops-60378},
  doi =		{10.4230/LIPIcs.SWAT.2016.15},
  annote =	{Keywords: Algorithms and data structures, disjoint paths, treewidth}
}

Search Results

Documents authored by Risteski, Andrej

On Routing Disjoint Paths in Bounded Treewidth Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message