Algorithms – ESA 2005

This volume contains the 75 contributed papers and the abstracts of the three invited lectures presented at the 13th Annual European Symposium on Al- rithms (ESA 2005), held in Palma de Mallorca, Spain, October 3-6, 2005. The threedistinguishedinvitedspeakerswereGiuseppeF.Italiano,CristopherMoore and Joseph (Se?) Naor. Since 2002,ESA has consisted of two tracks, with separate programcomm- tees, which dealt respectively with - the designandmathematicalanalysis ofalgorithms(the "DesignandAna- sis" track); - real-worldapplications, engineering and experimental analysis of algorithms (the "Engineering and Applications" track). Previous ESAs in the current two track format were held in Rome, Italy (2002);Budapest,Hungary(2003);andBergen,Norway(2004).Theproceedings of these symposia were published as Springer's LNCS volumes 2461, 2832, and 3221 respectively. Papers were solicited in all areas of algorithmic research, including but not limited to algorithmic aspects of networks, approximation and on-line al- rithms, computational biology, computational geometry, computational ?nance and algorithmic game theory, data structures, database and information - trieval, external memory algorithms, graph algorithms, graph drawing, machine learning, mobile computing, pattern matching and data compression, quantum computing, and randomized algorithms.The algorithms could be sequential, distributed, or parallel. Submissions were especially encouraged in the area of mathematical programming and operations research, including combinatorial optimization, integer programming, polyhedral combinatorics, and semide?nite programming.