A Note on the Complexity of Sliding Shortest Paths

Engels, Birgit and Pardella, Gregor (2009) A Note on the Complexity of Sliding Shortest Paths.
Technical Report , 4 p.


We address a shortest path problem in a given uncapacited and undirected network N=(V,E) with positive edge costs. In addition we are given a single source-destination pair (s,t), a shortest path p{st} connecting s and t and a new edge e =(p,q). The task is to find a minimum number of edges Ec and the minimum weight increase for each edge e in Ec such that the shortest path p{st} between s and t traverses edge e. We show that the problem is NP-hard and give a heuristic scheme for the problem.

Download: [img] Postscript
Download (253kB) | Preview
Download: [img] PDF
Download (94kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2009-594
Depositing User: Birgit Engels
Date Deposited: 03 Dec 2009 00:00
Last Modified: 09 Jan 2012 15:35
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/594