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.
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.63-74, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00359710
Contributeur : Publications Loria <>
Soumis le : lundi 9 février 2009 - 11:27:24
Dernière modification le : mercredi 29 novembre 2017 - 10:27:36
Document(s) archivé(s) le : mardi 8 juin 2010 - 22:05:24

Fichier

05-ahmed.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00359710, version 1

Collections

Citation

Mustaq Ahmed, Anna Lubiw. Shortest Paths Avoiding Forbidden Subpaths. Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.63-74, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00359710〉

Partager

Métriques

Consultations de la notice

88

Téléchargements de fichiers

225