HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
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

156

Files downloads

273