ESA Test-of-Time Award 2015

___________________________________________________________________________________
Announcement of the ESA Test-of-Time Award 2015

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.

The award committee selected the following two papers for the ESA ToTA 2015.
The papers stand out for their impact and wide use in the algorithms field, and for their excellent citation records up to the present day.

From ESA 03-95:

Mechthild Stoer, Frank Wagner:
A Simple Min Cut Algorithm
Proceedings ESA'94, also in: JACM 44:4 (1997) 585-591

Laudatio
The minimum cut problem in graphs is a basic problem in network analysis
and is needed, for example, as the separation routine in branch-and-cut
algorithms for the Traveling Salesman problem. Stoer and Wagner gave an
elegant and efficient algorithm for the problem that avoids the computation
of maximum flows, building upon previous work by Nagamochi and Ibaraki. The
same algorithm was independently found by Frank. The algorithm continues to
be taught because of its elegance and used because of its efficiency and ease
of implementation.

From ESA 94-96:

Sudipto Guha, Samir Khuller:
Approximation Algorithms for Connected Dominating Sets
Proceedings ESA'96, also in: Algorithmica 20:4 (1998) 374-387

Laudatio
It is natural to require connectedness as an additional constraint for a
dominating set, for example, in ad hoc wireless networks. Domination
guarantees coverage and connectedness guarantees communication between
the selected nodes. Guha and Khuller gave polynomial algorithms for a
logarithmic-factor approximation to its solution. Under the usual
assumptions, this is the best possible. Their much-cited work has
stimulated similar research for connected variants of many other graph
problems.

Exceptionally, in this first year in which award is given, the
ESA ToTA 2015 committee was asked to consider all qualifying papers from
ESA 93-95 and ESA 94-96, respectively.

Award Committee: Jan van Leeuwen, Kurt Mehlhorn and Mike Paterson
_________________________________________________________________________________________