ISSN:
1436-5057
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Abstract The following algorithm for finding thek-shortest loopless paths from one node to another is a development of the algorithm published in [2]. Though memory need is less, the new algorithm is running is bout 20 times as fast on large networks (1000 nodes and more). The computer time increases linearly withk and about quadratic with the number of nodes on the generated paths.
Notes:
Zusammenfassung Der in der vorliegenden Arbeit vorgestellte Algorithmus zur Ermittlung vonk-kürzesten schleifenfreien Kantenfolgen von einem Anfangsknoten zu einem Endknoten stellt eine Weiterentwicklung des in [2] beschriebenen Verfahrens dar. Bei deutlich geringerem Speicherplatzbedarf konnte die Rechengeschwindigkeit stark gesteigert werden (bei Graphen von 1000 Knoten ungefähr um das 20fache). Die Rechenzeit wächst linear mitk und in etwa quadratisch mit der Knotenzahl der erzeugten Wege.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02241985
