Shortest Paths Avoiding Forbidden Subpaths

Simple item page
dc.creatorAhmed, Mustaq
dc.creatorLubiw, Anna
dc.date2008-07-04
dc.date2009-02-11
dc.date.accessioned2026-07-07T12:39:43Z
dc.date.available2026-07-07T12:39:43Z
dc.descriptionIn 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 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.
dc.description12 pages, 2 figures. Fixed a few typos, rephrased a few sentences, and used the STACS style
dc.identifierhttps://arxiv.org/abs/0807.0807
dc.identifierhttp://arxiv.org/abs/0807.0807
dc.identifierProceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS), Freiburg, Germany, 2009, pp. 63-74
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/219210
dc.subjectDiscrete Mathematics
dc.subjectData Structures and Algorithms
dc.subjectG.2.2; F.2.2
dc.titleShortest Paths Avoiding Forbidden Subpaths
dc.typetext

Files

Collections

arXiv