ESA 2004

12th Annual European Symposium on Algorithms

Radisson SAS Royal Hotel, Bergen, Norway, September 14-17, 2004


The Symposium covers research in the use, design and analysis of efficient algorithms and data structures in computer science, discrete applied mathematics, operations research and mathematical programming. The Symposium has two tracks, which deal respectively with: ESA 2004 is sponsored by EATCS (the European Association for Theoretical Computer Science) and jointly organized with WABI 2004, WAOA 2004, IWPEC 2004 and ATMOS 2004 in the context of ALGO 2004. For updated information see the web site


Papers presenting original research in all areas of algorithmic research are sought, including but not limited to computational biology, computational finance, computational geometry, databases and information retrieval, external-memory algorithms, graph and network algorithms, graph drawing, machine learning, network design, on-line algorithms, parallel and distributed computing, pattern matching and data compression, quantum computing, randomized algorithms, and symbolic computation. The algorithms may be sequential, distributed or parallel.

Submissions are especially encouraged in the areas of mathematical programming and operations research, including approximation algorithms, branch-and-cut algorithms, combinatorial optimization, integer programming, network optimization, polyhedral combinatorics, and semidefinite programming.


Authors are invited to submit an extended abstract or full paper of at most 12 pages in LNCS-style. The paper should contain a succinct statement of the issues and of their motivation, a summary of the main results, and a brief explanation of their significance, accessible to non-specialist readers. Proofs omitted due to space constraints must be put into an appendix to be read by the program committee members at their discretion. For type-setting submissions in LNCS-style, it is recommended that the authors use latex2e, the style file llncs.cls, and the document-class option runningheads. The general style parameters like the size of the page and margins and the size of fonts should not be changed. The most relevant part of the sample latex source file llncs.dem starts where the command \title is. Electronic submission is highly recommended; procedures for electronic submission may be found at the following URLs.

The postscript file must be received by April 2, 2004, 23:59 GMT to be considered. In case of problems with access to internet, it is possible to submit 6 copies of the paper to the appropriate program committee chair.

Design and Analysis Track:
Susanne Albers
Institut fuer Informatik
Albert-Ludwigs-Universitaet Freiburg
Georges-Koehler-Allee 79
D-79110 Freiburg, Germany

Engineering and Applications Track:
Tomasz Radzik
Department of Computer Science
King's College London
London WC2R 2LS, UK

Hard copy submissions must be received by April 2 or postmarked no later than March 26 and sent by airmail to be considered. Authors are expected to present their accepted papers at the conference.


Simultaneous submission to other conferences with published proceedings, or to both tracks of ESA 2004, is not permitted. A paper submitted to one track of ESA 2004 may be switched to the other track if, in the opinion of the PC chairs, the paper is better suited to the other track.


EATCS sponsors an award for the best student paper at ESA 2004. All of a paper's authors must be students for the paper to be considered for this award. Please indicate "student paper" on the front page of the submission if all authors are students.



Accepted papers will be published in the Springer series Lecture Notes in Computer Science. Previous proceedings of ESA, 2001 in Aarhus, 2002 in Rome and 2003 in Budapest, appeared as LNCS 2161, 2461 and 2832. Previous proceedings of the precursor to the Engineering and Applications track, the Workshop on Algorithm Engineering, held in 1999 in London, 2000 in Saarbruecken and 2001 in Aarhus, appeared as LNCS 1668, 1982 and 2141. Accepted contributed papers will receive an allotment of 12 pages in the proceedings.


Design and Analysis Track
Karen Aardal, Georgia Institute of Technology
Susanne Albers, University of Freiburg (Chair)
Timothy Chan, University of Waterloo
Camil Demetrescu, University of Rome "La Sapienza"
Rolf Fagerberg, BRICS Aarhus
Paolo Ferragina, University of Pisa
Fedor Fomin, University of Bergen
Claire Kenyon, Ecole Polytechnique
Elias Koutsoupias, University of Athens and UCLA
Klaus Jansen, University of Kiel
Ulrich Meyer, MPI Saarbruecken
Michael Mitzenmacher, Harvard University
Joseph (Seffi) Naor, Technion, Haifa
Micha Sharir, Tel Aviv University
Peter Widmayer, ETH Zurich
Gerhard Woeginger, University of Twente and TU Eindhoven

Engineering and Applications Track
Bo Chen, University of Warwick
Ulrich Derigs, University of Cologne
Andrew V. Goldberg, Microsoft Research
Roberto Grossi, University of Pisa
Giuseppe F. Italiano, University of Rome "Tor Vergata"
Giuseppe Liotta, University of Perugia
Tomasz Radzik, King's College London (Chair)
Marie-France Sagot, INRIA Rhone-Alpes
Christian Scheideler, Johns Hopkins University
Jop F. Sibeyn, University of Halle
Michiel Smid, Carleton University


Eivind Coward, University of Bergen
Fedor Fomin, University of Bergen (Co-chair)
Pinar Heggernes, University of Bergen (Chair)
Inge Jonassen, University of Bergen
Fredrik Manne, University of Bergen
Jan Arne Telle, University of Bergen