DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2009.1831

Shortest Paths Avoiding Forbidden Subpaths

Authors: Mustaq Ahmed and Anna Lubiw

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract

In this paper we study a variant of the shortest path problem in graphs: given a weighted graph $G$ and vertices $s$ and $t$, and given a set $X$ of forbidden paths in $G$, find a shortest $s$-$t$ path $P$ such that no path in $X$ is a subpath of $P$. Path $P$ is allowed to repeat vertices and edges. We call each path in $X$ an \emph{exception}, and our desired path a \emph{shortest exception avoiding path}. We formulate a new version of the problem where the algorithm has no a priori knowledge of $X$, and finds out about an exception $x \in X$ only when a path containing $x$ fails. This situation arises in computing shortest paths in optical networks. We give an algorithm that finds a shortest exception avoiding path in time polynomial in $|G|$ and $|X|$. The main idea is to run Dijkstra's algorithm incrementally after replicating vertices when an exception is discovered.

Cite as

Mustaq Ahmed and Anna Lubiw. Shortest Paths Avoiding Forbidden Subpaths. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 63-74, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{ahmed_et_al:LIPIcs.STACS.2009.1831,
  author =	{Ahmed, Mustaq and Lubiw, Anna},
  title =	{{Shortest Paths Avoiding Forbidden Subpaths}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{63--74},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1831},
  URN =		{urn:nbn:de:0030-drops-18318},
  doi =		{10.4230/LIPIcs.STACS.2009.1831},
  annote =	{Keywords: Algorithms and data structures, Graph algorithms, Optical networks}
}

Search Results

Documents authored by Ahmed, Mustaq

Shortest Paths Avoiding Forbidden Subpaths

Abstract

Cite as

Thanks for your feedback!

Could not send message