Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
http://dx.doi.org/10.18419/opus-2678
Langanzeige der Metadaten
DC Element | Wert | Sprache |
---|---|---|
dc.contributor.author | Lewandowski, Stefan | de |
dc.date.accessioned | 2010-09-10 | de |
dc.date.accessioned | 2016-03-31T07:58:58Z | - |
dc.date.available | 2010-09-10 | de |
dc.date.available | 2016-03-31T07:58:58Z | - |
dc.date.issued | 2010 | de |
dc.identifier.other | 381639126 | de |
dc.identifier.uri | http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-56741 | de |
dc.identifier.uri | http://elib.uni-stuttgart.de/handle/11682/2695 | - |
dc.identifier.uri | http://dx.doi.org/10.18419/opus-2678 | - |
dc.description.abstract | Since 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.iso | en | de |
dc.relation.ispartofseries | Technischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik;2010,5 | de |
dc.rights | info:eu-repo/semantics/openAccess | de |
dc.subject.classification | Kürzester-Weg-Problem | de |
dc.subject.ddc | 004 | de |
dc.subject.other | shortest path , negative weights , negative cycle detection | en |
dc.title | Shortest paths and negative cycle detection in graphs with negative weights. I, The Bellman-Ford-Moore algorithm revisited | en |
dc.type | workingPaper | de |
dc.date.updated | 2011-09-05 | de |
ubs.fakultaet | Fakultät Informatik, Elektrotechnik und Informationstechnik | de |
ubs.institut | Institut für Formale Methoden der Informatik | de |
ubs.opusid | 5674 | de |
ubs.publikation.typ | Arbeitspapier | de |
ubs.schriftenreihe.name | Technischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik | de |
Enthalten in den Sammlungen: | 05 Fakultät Informatik, Elektrotechnik und Informationstechnik |
Dateien zu dieser Ressource:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
TR_2010_05.pdf | 705,12 kB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repositorium sind urheberrechtlich geschützt.