Universität zu Köln

Engels, Birgit and Pardella, Gregor (2009). A Note on the Complexity of Sliding Shortest Paths. Working Paper.

Preview

PDF zaik2009-594.pdf Download (94kB) | Preview

Abstract

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.

Item Type:	Preprints, Working Papers or Reports (Working Paper)
Creators:	Creators Email ORCID ORCID Put Code Engels, Birgit UNSPECIFIED UNSPECIFIED UNSPECIFIED Pardella, Gregor UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-549897
Date:	2009
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54989