Algorithms - ESA 2010 : 18th annual European symposium, Liverpool, UK, September 6-8, 2010 : proceedings, part II

This volume contains the 69 papers presented at the 16th Annual European Symposium on Algorithms (ESA 2010), held in Liverpool during September 6–8, 2010, including three papers by the distinguished invited speakers Artur Czumaj, Herbert Edelsbrunner, and Paolo Ferragina. ESA 2010 was organized as a part of ALGO 2010, which also included the 10th Workshop on Algorithms in Bioinformatics (WABI), the 8th Workshop on Approximation and Online Algorithms (WAOA), and the 10th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS). The European Symposium on Algorithms covers research in the design, use, and analysis of efficient algorithms and data structures. As in previous years, the symposium had two tracks: the Design and Analysis Track and the Engineering and Applications Track, each with its own Program Committee. In total 245 papers adhering to the submission guidelines were submitted. Each paper was reviewed by three or four referees. Based on the reviews and the often extensive electronic discussions following them, the committees selected 66 papers in total: 56 (out of 206) to the Design and Analysis Track and 10 (out of 39) to the Engineering and Applications track.We believe that these papers together made up a strong and varied program, showing the depth and breadth of current algorithms research. Three papers deserve special mentioning: the papers "When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings" by N. Bansal, A. Gupta, J. Li, J. Mestre, V. Nagarajan and A. Rudra and "Feasibility Analysis of Sporadic Real-Time Multiprocessor Task Systems" by V. Bonifaci and A. Marchetti-Spaccamela, which won the award for the best paper, and the paper "Shortest Paths in Planar Graphs with Real Lengths in O(n log2 n/ log log n) Time" by S. Mozes and C. Wulff-Nilsen, which won the award for the best student paper. We congratulate the authors on this succes. ESA 2010 was sponsored by the European Association of Theoretical Computer Science, the International Society of Computational Geometry, the London Mathematical Society, Springer, and the University of Liverpool. Besides the sponsors, we also wish to thank the people from the EasyChair Conference System; using their wonderful system saved us an enormous amount of work during the whole process. Finally, we thank all authors who submitted their work to ESA 2010, all Program Committee members for their hard work, and all reviewers who helped the Program Committees in evaluating the submitted papers, and we hope the readers will find the papers in these proceedings instructive and enjoyable