This volume contains the 70 contributed papers and abstracts of 3 of the 5 invited talks presented at the 14th Annual Symposium on Algorithms (ESA 2006), held at ETH Zurich in Zurich, Switzerland, September 11 13, 2006. The papers in each section of the proceedings are arranged alphabetically. The ?ve distinguished invitedspeakerswereErik Demaine, Lisa Fleischer, Laszl oLovasz, Kurt Mehlhorn, and Ron Shamir. Since 2002, ESA has consisted of two tracks, with separate Program C- mittees, which deal respectively with: The design and mathematical analysis of algorithms (the Design and An- ysis track) Real-worldapplications, engineering, andexperimentalanalysisofalgorithms (the Engineering and Applications track) Previous ESAs in the current two-track format were held in Rome, Italy (2002); Budapest, Hungary (2003); Bergen, Norway (2004); and Palma de Mallorca, Spain (2005). The proceedings of these symposia were published as Springer s LNCS volumes 2461, 2832, 3221 and 3669, 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 ?nance and algorithmic game theory, computational geometry, data structures, databases and information - trieval, external-memoryalgorithms, graphandnetworkalgorithms, graphdr- ing, machine learning, mobile and distributed computing, pattern matching and data compression, quantum computing, and randomized algorithms. The al- rithms 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 com- natorics and network optimization.q... 30000 40000 50000 60000 70000 Number of edges DI0.7 T16 Experiment on random inputs (500 vertices, increasing m) 0 100 200 300 400 500 600 ... The top chart of Figure 3 shows the time and space requirements of T16 and DI0.7 on anbsp;...
|Title||:||Algorithms - ESA 2006|
|Author||:||Yossi Azar, Thomas Erlebach|
|Publisher||:||Springer Science & Business Media - 2006-08-31|