Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-2678
Full metadata record
DC FieldValueLanguage
dc.contributor.authorLewandowski, Stefande
dc.date.accessioned2010-09-10de
dc.date.accessioned2016-03-31T07:58:58Z-
dc.date.available2010-09-10de
dc.date.available2016-03-31T07:58:58Z-
dc.date.issued2010de
dc.identifier.other381639126de
dc.identifier.urihttp://nbn-resolving.de/urn:nbn:de:bsz:93-opus-56741de
dc.identifier.urihttp://elib.uni-stuttgart.de/handle/11682/2695-
dc.identifier.urihttp://dx.doi.org/10.18419/opus-2678-
dc.description.abstractSince the mid 1950's when Bellman, Ford, and Moore developped their shortest path algorithm various attempts were made to beat the O(nm) barrier without success. For the special case of integer weights Goldberg's algorithm gave a theoretical improvement, but the algorithm isn't competative in praxis. This technical report is part one of a summary of existing n-pass algorithms and some new variations. In this part we consider the classical algorithm and variations that differ only in the data structure used to maintain the set of nodes to be scanned in the current and following pass. We unify notation and give some experimental results for the average case on various graph classes.en
dc.language.isoende
dc.relation.ispartofseriesTechnischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik;2010,5de
dc.rightsinfo:eu-repo/semantics/openAccessde
dc.subject.classificationKürzester-Weg-Problemde
dc.subject.ddc004de
dc.subject.othershortest path , negative weights , negative cycle detectionen
dc.titleShortest paths and negative cycle detection in graphs with negative weights. I, The Bellman-Ford-Moore algorithm revisiteden
dc.typeworkingPaperde
dc.date.updated2011-09-05de
ubs.fakultaetFakultät Informatik, Elektrotechnik und Informationstechnikde
ubs.institutInstitut für Formale Methoden der Informatikde
ubs.opusid5674de
ubs.publikation.typArbeitspapierde
ubs.schriftenreihe.nameTechnischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnikde
Appears in Collections:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:
File Description SizeFormat 
TR_2010_05.pdf705,12 kBAdobe PDFView/Open


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