Skip to Main content Skip to Navigation
Conference papers

Shortest Paths Avoiding Forbidden Subpaths

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 exception, and our desired path a 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 ∈ 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.
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/inria-00359710
Contributor : Publications Loria <>
Submitted on : Monday, February 9, 2009 - 11:27:24 AM
Last modification on : Wednesday, November 29, 2017 - 10:27:36 AM
Long-term archiving on: : Tuesday, June 8, 2010 - 10:05:24 PM

File

05-ahmed.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00359710, version 1

Collections

Citation

Mustaq Ahmed, Anna Lubiw. Shortest Paths Avoiding Forbidden Subpaths. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. pp.63-74. ⟨inria-00359710⟩

Share

Metrics

Record views

224

Files downloads

468