List of accepted papers for ESA 2006

Design and Analysis Track

• Less 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
  Sureander 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