Announcement of the ESA Test-of-Time Award 2017
European Symposium on Algorithms (ESA)
http://esa-symposium.org/
___________________________________________________________________________________
The ESA Test-of-Time Award (ESA ToTA) recognizes outstanding 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 2017 award, papers from ESA'96 to ESA'98 were
considered.
The committee nominates the following paper for the ESA ToTA 2017. The
paper stands out as a classic in the algorithms field and continues to
be cited as an exemplary study in its field.
>From ESA 96-98:
James Abello, Adam L. Buchsbaum, and Jeffery R. Westbrook
A Functional Approach to External Graph Algorithms
Proceedings ESA'98, pp. 332-343
also in: Algorithmica 32 (2002) 437-458
Laudation:
The paper deals with the design of algorithms that operate on massive
data sets in external memory. Building on the well-known I/O model of
complexity by Aggarwal and Vitter, the authors introduce a novel
design principle for external algorithms based purely on functional
transformations of the data, which facilitates standard checkpointing
and program optimization techniques. Illustrated on a variety of graph
problems, their approach is proved to be elegant and versatile in the
design of both deterministic and randomized external algorithms while
the resulting I/O complexities remain competitive. Functional
algorithms are also designed for semi-external problems, in which the
nodes fit in main memory but the connecting edges are abundant and
only available in external memory. The paper is an excellent
illustration of how general principles of functional program design
and model-based complexity can remain in harmony in the field of
external algorithms.
Award Committee: Giuseppe F. Italiano (Rome), Mike Paterson (Warwick),
Jan van Leeuwen (Utrecht)
_____________________
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
