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 |
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.