Premium
Shortest paths avoiding forbidden subpaths
Author(s) -
Ahmed Mustaq,
Lubiw Anna
Publication year - 2013
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21490
Subject(s) - shortest path problem , distance , k shortest path routing , combinatorics , yen's algorithm , longest path problem , euclidean shortest path , constrained shortest path first , shortest path faster algorithm , widest path problem , path (computing) , mathematics , discrete mathematics , computer science , graph , dijkstra's algorithm , computer network
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 use a shortest path algorithm incrementally after replicating vertices when an exception is discovered. © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2013