The Complexity of an Inverse Shortest Path Problem
Fekete, Sandor P. and Hochstättler, Winfried and Kromberg, Stephan and Moll, Christoph
(1999)
The Complexity of an Inverse Shortest Path Problem.
Published In:
Contemporary trends in discrete mathematics : from DIMACS and DIMATIA to the future ; DIMATIADIMACS conference, May 19  25, 1997, Štiřín Castle, Czech Republic ; [contains papers from a DIMATIA/DIMACS Conference on the Future of Discrete Mathematics], DIMACS series in discrete mathematics and theoretical computer science. 49 American Mathematical Society (AMS) 1999, pp. 113127.
Abstract
In this paper we study the complexity of an Inverse Shortest Paths Problem (ISPP). We show that this problem is intractable even in very restricted cases. In particular, we prove that this Inverse Shortest Paths Problem is NPcomplete in the planar case. Furthermore, we give a characterization of the class of graphs Gd of given distances for which the ISPP is tractable: we give polynomial algorithms for special classes of Gd and provide evidence that no polynomial time algorithms exist if the structure of Gd is only slightly more complicated in a welldefined graphtheoretical sense. Finally, we discuss the situation for directed graphs.
Download: 
Postscript
 Preprinted Version
Download (334kB)  Preview 

Editorial actions:  View Item (Login required) 
Item Type:  Proceedings article 

Citations:  19 (Google Scholar)  
Uncontrolled Keywords:  computational complexity distance in graphs inverse shortest path problem NPcompleteness planar graphs shortest paths 
Subjects: 

Divisions:  Mathematical Institute 
Related URLs: 
ZAIK Number:  zpr96226 

Depositing User:  Winfried Hochstättler 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  16 Jan 2012 14:26 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/226 