Computer Science – Discrete Mathematics
Scientific paper
2008-07-04
Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS), Freiburg, Germany, 2009, p
Computer Science
Discrete Mathematics
12 pages, 2 figures. Fixed a few typos, rephrased a few sentences, and used the STACS style
Scientific paper
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 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.
Ahmed Mustaq
Lubiw Anna
No associations
LandOfFree
Shortest Paths Avoiding Forbidden Subpaths does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Shortest Paths Avoiding Forbidden Subpaths, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shortest Paths Avoiding Forbidden Subpaths will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-598231