List of accepted papers for ESA 2006: Design and Analysis: TrackLess Hashing, Same Performance: Building a Better Bloom Filter Adam Kirsch and Michael Mitzenmacher Estimating Entropy over Data Streams Lakshminath Bhuvanagiri and Sumit Ganguly Violator Spaces: Structure and Algorithms Bernd Gaertner, Jiri Matousek, Leo Ruest, Petr Skovron Approximation results for preemptive stochastic online scheduling Nicole Megow and Tjark Vredeveld Resource Allocation in Bounded Degree Trees Reuven Bar-Yehuda and Michael Beder and Yuval Cohen and Dror Rawitz A Unified Approach to Approximating Partial Covering Problems Jochen Konemann and Ojas Parekh and Danny Segev Path Hitting in Acyclic Graphs Ojas Parekh and Danny Segev Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games Bruno Codenotti and Mauro Leoncini and Giovanni Resta Approximating almost all instances of Max­Cut within a ratio above the Hastad threshold A.C. Kaporis and L.M. Kirousis and E.C. Stavropoulos Dynamic Programming and Fast Matrix Multiplication Frederic Dorn Graph coloring with rejection Leah Epstein and Asaf Levin and Gerhard J. Woeginger Region-Restricted Clustering for Geographic Data Mining Joachim Gudmundsson and Marc van Kreveld and Giri Narasimham Deciding Relaxed Two-Colorability - A Hardness Jump Robert Berke and Tibor Szabo I/O-Efficient Undirected Shortest Paths with Unbounded Weights Ulrich Meyer and Norbert Zeh An O(n^3 (log log n/ log n)^5/4 ) Time Algorithm for All Pairs Shortest Path Yijie Han Cooperative TSP Amitai Armon and Adi Avidor and Oded Schwartz Negative Examples for Sequential Importance Sampling of Binary Contingency Tables Ivona Bezakova and Alistair Sinclair and Daniel Stefankovic and Eric Vigoda Navigating Low-Dimensional and Hierarchical Population Networks Ravi Kumar and David Liben-Nowell and Andrew Tomkins Approximate $k$-Steiner Forests via the Lagrangian Relaxation Technique with Internal Preprocessing Danny Segev and Gil Segev Minimum Transversals in Posi-modular Systems Mariko Sakashita and Kazuhisa Makino and Hiroshi Nagamochi and Satoru Fujishige A doubling dimension threshold theta(loglogn) for augmented graphs navigability Pierre Fraigniaud and Emmanuelle Lebhar and Zvi Lotker Latency Constrained Aggregation in Sensor Networks Luca Becchetti and Peter Korteweg and Alberto Marchetti-Spaccamela and Martin Skutella and Leen Stougie and Andrea Vitaletti Competitive Analysis of Flash-Memory Algorithms Avraham Ben-Aroya and Sivan Toledo Kinetic Collision Detection for Convex Fat Objects Mohammad Ali Abam and Mark de Berg and Sheung-Hung Poon and Bettina Speckmann Preemptive Online Scheduling: Optimal Algorithms for All Speeds Tomas Ebenlendr, Wojciech Jawor, Jiri Sgall Spanners with Slack T-H. Hubert Chan and Michael Dinitz and Anupam Gupta Lower and Upper Bounds on FIFO Buffer Management in QoS Switches Matthias Englert and Matthias Westermann On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization Khaled Elbassioni Distributed almost exact approximations for minor-closed families Andrzej Czygrinow and Michal Hanckowiak Purely Functional Worst Case Constant Time Catenable Sorted Lists Gerth Brodal, Christos Makris, Kostas Tsichlas Greedy in Approximation Algorithms Julian Mestre Balancing Applied to Maximum Network Flow Problems Robert Tarjan, Julie Ward, Bin Zhang, Yunhong Zhou and Jia Mao Traversing the Machining Graph Danny Z. Chen and Rudolf Fleischer and Jian Li and Haitao Wang Enumerating Spanning and Connected Subsets in Graphs and Matroids L. Khachiyan and E. Boros and K. Borys and K. Elbassioni and V. Gurvich and K. Makino Popular Matchings in the Capacitated House Allocation Problem David F. Manlove and Colin T.S. Sng Dynamic Algorithms for Maintaining Graph Spanners Surender Baswana Single machine precedence constrained scheduling is a vertex cover problem Christoph Ambuhl and Monaldo Mastrolilli Frechet Distance for Curves, Revisited Boris Aronov and Sariel Har-Peled and Christian Knauer and Yusu Wang and Carola Wenk Inner-Product Based Wavelet Synopses for Range-Sum Queries Yossi Matias and Daniel Urieli Cheating by Men in the Gale-Shapley Stable Matching Algorithm Chien-Chung Huang Dynamic Connectivity for Axis-Parallel Rectangles Peyman Afshani and Timothy M. Chan Contention Resolution with Heterogeneous Job Sizes Michael A. Bender and Jeremy T. Fineman and Seth Gilbert Finding total unimodularity in optimization problems solved by linear programs Christoph Dürr and Mathilde Hurand Near-Entropy Hotlink Assignments Karim Douïeb and Stefan Langerman Stochastic Shortest Paths via Quasi-Convex Maximization Evdokia Nikolova and Jonathan A. Kelner and Matthew Brand and Michael Mitzenmacher Subspace Sampling and Relative-Error Matrix Approximation: Column-Row-Based Methods Petros Drineas and Michael W. Mahoney and S. Muthukrishnan Compressed Indexes for Approximate String Matching Ho-Leung Chan and Tak-Wah Lam and Wing-Kin Sung and Siu-Lung Tam and Swee-Seong Wong Spectral Clustering by Recursive Partitioning Anirban Dasgupta and John Hopcroft and Ravi Kannan and Pradipta Mitra Taxes for linear atomic congestion games Ioannis Caragiannis and Christos Kaklamanis and Panagiotis Kanellopoulos Finite Termination of "Augmenting Path" Algorithms in the Presence of Irrational Problem Data Brian C. Dean and Michel X. Goemans and Nicole Immorlica An LP-Designed Algorithm for Constraint Satisfaction Alexander D. Scott and Gregory B. Sorkin Necklaces, Convolutions, and X+Y David Bremner and Timothy M. Chan and Erik D. Demaine and Jeff Erickson and Ferran Hurtado and John Iacono and Stefan Langerman and Ileana Streinu and Perouz Taslakian Engineering and Applications Track: An MINLP solution method for a water network problem Cristiana Bragalli and Claudia D'Ambrosio and Jon Lee and Andrea Lodi and Paolo Toth Exact and Efficient Construction of Planar Minkowski Sums using the Convolution Method Ron Wein Multiline Addressing by Network Flow Friedrich Eisenbrand and Andreas Karrenbauer and Martin Skutella and Chihao Xu Robust, Generic and Efficient Construction of Envelopes of Surfaces in Three-Dimensional Space Michal Meyerovitch Parallel machine scheduling through column generation: minimax objective functions J.M. van den Akker and J.A. Hoogeveen and J.W. van Kempen On exact algorithms for treewidth Hans L. Bodlaender and Fedor V. Fomin and Arie M. C. A. Koster and Dieter Kratsch and Dimitrios M. Thilikos An Improved Construction for Counting Bloom Filters Flavio Bonomi and Michael Mitzenmacher and Rina Panigrahy and Sushil Singh and George Varghese How Branch Mispredictions Affect Quicksort Kanela Kaligosi and Peter Sanders Reporting Flock Patterns Marc Benkert and Joachim Gudmundsson and Florian Huebner and Thomas Wolle Engineering Highway Hierarchies Peter Sanders and Dominik Schultes Univariate polynomial real root isolation: Continued Fractions revisited Iaonnis Z. Emiris and Elias P. Tsigaridas Algorithmic Aspects of Proportional Symbol Maps Sergio Cabello and Herman Haverkort and Marc van Kreveld and Bettina Speckmann Kinetic Algorithms via Self-Adjusting Computation Umut A. Acar and Guy E. Blelloch and Kanat Tangwongsan and Jorge L. Vittes Out-of-Order Event Processing in Kinetic Data Structures Mohammad Ali Abam and Pankaj K. Agarwal and Mark de Berg and Hai Yu Skewed Binary Search Trees Gerth S. Brodal and Gabriel Moruz The Price of Resiliency: A Case Study on Sorting with Memory Faults Umberto Ferraro Petrillo and Irene Finocchi and Giuseppe F. Italiano Does Path Cleaning Help in Dynamic All-Pairs Shortest Paths? Camil Demetrescu, Pompeo Faruolo, Giuseppe F. Italiano, Mikkel Thorup The Engineering of a Compression Boosting Library: Theory vs Practice in BWT compression P. Ferragina and R. Giancarlo and G. Manzini