COMPUTING STRICTLY-SECOND SHORTEST PATHS

Authors
LALGUDI KN PAPAEFTHYMIOU MC
Citation
Kn. Lalgudi et Mc. Papaefthymiou, COMPUTING STRICTLY-SECOND SHORTEST PATHS, Information processing letters, 63(4), 1997, pp. 177-181
Citations number
5
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
63
Issue
4
Year of publication
1997
Pages
177 - 181
Database
ISI
SICI code
0020-0190(1997)63:4<177:CSSP>2.0.ZU;2-K
Abstract
We investigate the problem of computing the strictly-second shortest p ath connecting a given pair of vertices in a directed graph. We show t hat this problem is intractable when the path is restricted to be simp le. When cycles are allowed, we give an algorithm that solves it in as ymptotically the same number of steps as it takes to compute the short est path between the given vertex pair. (C) 1997 Elsevier Science B.V.