A note on shortest path problems with forbidden paths

Title: A note on shortest path problems with forbidden paths
Creator: Smith, Olivia J.; Savelsbergh, Martin W. P.
Relation: ARC
Relation: Networks Vol. 63, Issue 3, p. 239-242
Publisher Link: http://dx.doi.org/10.1002/net.21541
Publisher: Wiley-Blackwell Publishing Ltd
Resource Type: journal article
Date: 2014
Description: 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.
Subject: shortest path; forbidden path; dynamic programming; algorithm
Identifier: http://hdl.handle.net/1959.13/1067849
Identifier: uon:18496
Identifier: ISSN:0028-3045
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format