A note on shortest path problems with forbidden paths. Issue 3 (12th March 2014)

• Record Type: Journal Article
• Authors: Smith, Olivia J.; Savelsbergh, Martin W.P.
• Is Part Of: Networks. Volume 63:Issue 3(2014:May)
• Page Start: 239
• Page End: 242
• Publication Date: 2014-03-12
• Subjects: Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21541
• Languages: English
• ISSNs: 0028-3045

Abstract

<abstract abstract-type="main"> <title> <x xml:space="preserve">Abstract</x> </title> <p>We consider the variant of the shortest path problem in which a given set of paths is forbidden to occur as a subpath in an optimal path. We establish that the most‐efficient algorithm for its solution, a dynamic programming algorithm, has polynomial time complexity; it had previously been conjectured that the algorithm has pseudo‐polynomial time complexity. Furthermore, we show that this algorithm can be extended, without increasing its time complexity, to handle non elementary forbidden paths. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 63(3), 239–242 2014</p> </abstract>