Please use this identifier to cite or link to this item: http://hdl.handle.net/10316/11305
DC FieldValueLanguage
dc.contributor.authorSantos, José Luis-
dc.date.accessioned2009-09-07T10:24:18Z-
dc.date.available2009-09-07T10:24:18Z-
dc.date.issued2007-
dc.identifier.citationPré-Publicações DMUC. 07-07 (2007)en_US
dc.identifier.urihttp://hdl.handle.net/10316/11305-
dc.description.abstractThis paper focuses on algorithms to solve the k-shortest path problem. Three codes are described and compared on random generated and real-world networks. One million paths were ranked in less than 3 seconds (3 microseconds per path), with at most 1 second of preprocessing, on random generated networks with 10 000 nodes. For real-world instances with more than one million nodes, the preprocessing time rises up to 2,7 hours and the CPU time to rank one million paths is less than 30 seconds (30 microseconds per path).en_US
dc.description.sponsorshipCentro de Matemática da Universidade de Coimbraen_US
dc.language.isoengen_US
dc.publisherCentro de Matemática da Universidade de Coimbraen_US
dc.rightsopenAccesseng
dc.subjectShortest pathen_US
dc.subjectRanking pathen_US
dc.subjectDeviation pathen_US
dc.titlek-Shortest path algorithmsen_US
dc.typepreprinten_US
uc.controloAutoridadeSim-
item.grantfulltextopen-
item.fulltextCom Texto completo-
item.languageiso639-1en-
crisitem.author.deptFaculty of Sciences and Technology-
crisitem.author.parentdeptUniversity of Coimbra-
crisitem.author.researchunitCMUC - Centre for Mathematics of the University of Coimbra-
crisitem.author.orcid0000-0002-2727-6774-
Appears in Collections:FCTUC Matemática - Vários
Files in This Item:
File Description SizeFormat
k-Shortest path algorithms.pdf192.72 kBAdobe PDFView/Open
Show simple item record

Page view(s)

204
checked on Sep 15, 2022

Download(s) 50

355
checked on Sep 15, 2022

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.