Shortest paths and negative cycle detection in graphs with negative weights. I, The Bellman-Ford-Moore algorithm revisited

Lewandowski, Stefan

Shortest paths and negative cycle detection in graphs with negative weights. I, The Bellman-Ford-Moore algorithm revisited

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.date.updated	2011-09-05	de
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.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.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
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

Files

Original bundle

Now showing 1 - 1 of 1

Name:: TR_2010_05.pdf
Size:: 705.12 KB
Format:: Adobe Portable Document Format

Download

License bundle

Now showing 1 - 1 of 1

Name:: license.txt
Size:: 1021 B
Format:: Plain Text
Description:

Download

Collections

05 Fakultät Informatik, Elektrotechnik und Informationstechnik