Finding next-to-shortest paths in a graph

Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/1677

Full metadata record

DC Field	Value	Language
dc.contributor.author	Krasikov, I	-
dc.contributor.author	Noble, S D	-
dc.coverage.spatial	4	en
dc.date.accessioned	2008-02-20T12:14:16Z	-
dc.date.available	2008-02-20T12:14:16Z	-
dc.date.issued	2004	-
dc.identifier.citation	Information Processing Letters, 92 (3): 117-119, Nov 2004	en
dc.identifier.issn	0020-0190	-
dc.identifier.uri	http://bura.brunel.ac.uk/handle/2438/1677	-
dc.description.abstract	We study the problem of finding the next-to-shortest paths in a graph. A next-to-shortest $(u,v)$-path is a shortest $(u,v)$-path amongst $(u,v)$-paths with length strictly greater than the length of the shortest $(u,v)$-path. In constrast to the situation in directed graphs, where the problem has been shown to be NP-hard, providing edges of length zero are allowed, we prove the somewhat surprising result that there is a polynomial time algorithm for the undirected version of the problem.	en
dc.format.extent	123747 bytes	-
dc.format.mimetype	application/pdf	-
dc.language.iso	en	-
dc.publisher	Elsevier	en
dc.subject	Graph algorithms	en
dc.subject	Computational complexity	en
dc.subject	Shortest paths	en
dc.title	Finding next-to-shortest paths in a graph	en
dc.type	Preprint	en
dc.identifier.doi	https://doi.org/10.1016/j.ipl.2004.06.020	-
Appears in Collections:	Computer Science Mathematical Sciences

Files in This Item:

File	Description	Size	Format
FullText.pdf		120.85 kB	Adobe PDF	View/Open