European Symposia on Algorithms

General information

The Symposium covers research in efficient algorithms and data structures in computer science, discrete applied mathematics, operations research and mathematical programming. Starting from 2002, the symposium has two tracks:

  • Design and Analysis Track

    Design and mathematical analysis of algorithms
  • Engineering and Application Track

    Real-world applications, engineering and experimental analysis of algorithms

The creation of two tracks in ESA follows the incorporation of the annual Workshop on Algorithm Engineering (WAE) into ESA.

Each track has its own program committee. Papers are submitted to a particular track, but the committees have the right to move papers between tracks.

In 2014, the ESA community decided to start an ESA Test-of-Time Award to recognize paper(s) from ESA Proceedings from 19-21 years ago which are still influential and stimulating for the field today.

News

  • The ESA Test-of-Time Award 2019 goes to

    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.

    more information

ESA Locations and Links