Test-of-Time Award

Peter Sanders erhält zusammen mit Ulrich Meyer (Universität Frankfurt) den "Test-of-Time"-Award 2019 des European Symposium on Algorithms (ESA), der auf der ESA 2020 verliehen wird. ESA ist die wichtigste europäische Konferenz zur Algorithmenforschung.
 

Der ESA Test-of-Time Award (ToTA) zeichnet exzellente Arbeiten aus, die in den ESA-Konferenzbänden vor 19 bis 21 Jahren erschienen und anhaltend einflussreich und stimulierend für die Algorithmenforschung sind. Für den Preis von 2019 hat das Preiskomitee die folgende Arbeit ausgewählt:

Ulrich Meyer, Peter Sanders
Delta-Stepping: A Parallel Single Source Shortest Path Algorithm.
https://ae.iti.kit.edu/sanders/papers/wmain.pdf
Proceedings of ESA 1998, pp. 393-404.

Ebenfalls erschienen in
J. Algorithms 49(1): 114-152 (2003)
https://www.sciencedirect.com/science/article/pii/S0196677403000762   

Laudatio des Preiskomitees (Englisch):
The paper presents an ingenious algorithm, dubbed Delta-stepping, for the Single-Source Shortest Path Problem (SSSP). This problem is well understood in the sequential setting (i.e., Dijkstra's algorithm) but its ubiquitous applications call for efficient parallelizations. Most of the sequential SSSP algorithms are based either on label-setting or on label-correcting methods. Label-setting algorithms, like Dijkstra's algorithm, settle at each iteration the distance label of one vertex. Label-correcting algorithms work instead by relaxing edges incident to unsettled vertices: all labels are temporary until the final step, when they all become permanent. In spite of the great practical performance of label-correcting methods, label-setting algorithms have been known to be asymptotically superior. In their paper, Meyer and Sanders show how to fill this gap by presenting Delta-stepping, a new label-correcting algorithm for SSSP which runs in optimal linear time with high probability for a large class of graphs with random edge weights. They further provide an efficient parallel implementation of their Delta-stepping algorithm, which has been a reference method and has inspired much subsequent work in parallel algorithms for many years.