ESA Test-of-Time Award 2019
The ESA Test-of-Time Award (ToTA) recognizes excellent papers in algorithms research that were published in the ESA proceedings 19-21 years ago and which are still influential and stimulating for the field today. For the 2019 Award, papers from ESA 1998 to ESA 2000 were considered. Because WAE merged in with ESA, the Steering Committee decided that the papers from WAE 1998 to WAE 2000 were also to be considered.
Ulrich Meyer, Peter Sanders
Delta-Stepping: A Parallel Single Source Shortest Path Algorithm.
Proceedings of ESA 1998, pp. 393-404.
Appeared also in J. Algorithms 49(1): 114-152 (2003)
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.
Award Committee: Giuseppe F. Italiano, Uri Zwick, Samir Khuller