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

Lewandowski, Stefan

Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-2678

Full metadata record

DC Field	Value	Language
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
Appears in Collections:	05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:

File	Description	Size	Format
TR_2010_05.pdf		705,12 kB	Adobe PDF	View/Open

Show simple item record

University of Stuttgart

OPUS - Publication Server of the University of Stuttgart