Test-of-Time Award

Peter Sanders (together with Ulrich Meyer from the University of Frankfurt) will be awarded the 'Test-of-Time Award' of the European Symposium on Algorithms 2019 (ESA) at ESA 2020.

ESA is the premier European conference on algorithms research. The ESA Test-of-Time Award (ToTA) recognizes excellent papers in algorithms research that were published in the ESA proceedings 19 to 21 years ago which are still influential and stimulating for the field today. For 2019, the Award Committee selected

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

Also appeared in
J. Algorithms 49(1): 114-152 (2003)
https://www.sciencedirect.com/science/article/pii/S0196677403000762 External Link   

Laudation of the Award Committee
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.