List of accepted papers for ESA 2004:


Design and Analysis Track: 

Dynamic Shannon Coding
Travis Gagie

Radio Network Clustering from Scratch
Fabian Kuhn, Thomas Moscibroda and Roger Wattenhofer

Approximation algorithms for quickest spanning tree problems
Refael Hassin and Asaf Levin

Fast sparse matrix multiplication
Raphael Yuster and Uri Zwick

Uniform Algorithms for Deterministic Construction of Efficient Disctinaries
Milan Ruzic

Tiling a polygon with two kinds of rectangles
Eric Remila

On variable-sized multidimensional packing
Leah Epstein and Rob van Stee

Improved Online Algorithms for Buffer Management in QoS Switches
Marek Chrobak, Wojciech Jawor, Jiri Sgall and Tomas Tichy

Approximate Unions of Lines and Minkowski Sums
Marc van Kreveld, A. Frank van der Stappen

Fast Multipoint Evaluation of Bivariate Polynomials
Michael Nüsken and Martin Ziegler

Faster fixed-parameter tractable algorithms for matching and packing problems
M. R. Fellows, C. Knauer, N. Nishimura, P. Ragde, F. Rosamond, U. Stege, D.M. Thilikos and S. Whitesides

Seeking a vertex of the planar matching polytope in NC
Raghav Kulkarni and Meena Mahajan

Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems
Reuven Cohen and David Peleg

On the Evolution of Selfish Routing
Simon Fischer and Berthold Voecking

Negotiation-Range Mechanisms: Coalition-Resistant Combinatorial Markets
Rica Gonen

Fractional covering with upper bounds on the variables: Solving LPs with negative entries
Naveen Garg and Rohit Khandekar

A Fast Distributed Algorithm for Approximating the Maximum Matching
Andrzej Czygrinow, Michal Hanckowiak and Edyta Szymanska

Hardness and Approximation Results for Packing Steiner Trees
Joseph Cheriyan and Mohammad R. Salavatipour

Flows on Few Paths: Algorithms and Lower Bounds
Maren Martens and Martin Skutella

A Parameterized Algorithm for Upward Planarity Testing
Hubert Chan

Load Balancing in Hypercubic Distributed Hash Tables with Heterogeneous Processors
Junning Liu and Micah Adler

Fisher Equilibrium Price with Concave Utility Functions
Ning Chen, Xiaotie Deng, Xiaoming Sun and Andrew Yao

Competitive online approximation of the optimal search ratio
Rudolf Fleischer, Tom Kamphans, Rolf Klein and Elmar Langetepe

Maximizing Throughput in Multi-Queue Switches
Y. Azar and A. Litichevskey

A Graph Decomposition Lemma and its Role in Metric Embedding
Yair Bartal

An improved algorithm for CIOQ switches
Y. Azar and Y. Richter

An approximation algorithm for maximum triangle packing
Refael Hassin and Shlomi Rubinstein

Fixed Parameter Algorithms for Counting and Deciding Bounded Restrictive list H-Colorings
Josep Diaz, Maria Serna and Dimitrios M. Thilikos

Time Dependent Multi Scheduling of Multicast
Rami Cohen, Dror Rawitz and Danny Raz

Approximate Parameterized Matching
Carmit Harel, Moshe Lewenstein and Dina Sokol

Approximation of rectangle stabbing and interval stabbing problems
Sofia Kovaleva and Frits Spieksma

On the stability of Multiple Partner Stable Marriages with ties
Varun S. Malhotra

Efficient Tradeoff Schemes in Data Structures for Querying Moving Objects
Pankaj K. Agarwal, Lars Arge, Jeff Erickson and Hai Yu

Incremental Algorithms for Facility Location and k-Median
Dimitris Fotakis

Fast 3-coloring Triangle-Free Planar Graphs
Lukasz Kowalik

Approximation Hardness of Dominating Set Problems
Miroslav Chlebik and Janka Chlebikova

Swap and Mismatch Edit Distance
Amihood Amir, Estrella Eisenberg and Ely Porat

Path Decomposition under a New Cost Measure with Applications to Optical Network Design
Elliot Anshelevich and Lisa Zhang

On dynamic shortest paths problems
Liam Roditty and Uri Zwick

Extreme Points under Random Noise
Valentina Damerow and Christian Sohler

Maximum Matching in Planar Graphs via Gaussian Elimination
Marcin Mucha and Piotr Sankowski

Modeling Locality: A Probabilistic Analysis of LRU and FWF
Luca Becchetti

Algorithms for Generating Minimal Blockers of Perfect Matchings in Bipartite Graphs and Related Problems
Endre Boros, Khaled Elbassioni and Vladimir Gurvich

Lower Bounds for Embedding into Distributions over Excluded Minor Graph Families
Douglas E. Carroll and Ashish Goel

Optimal External-Memory Planar Point Enclosure
Lars Arge, Vasilis Samoladas and Ke Yi

On adaptive integer sorting
Anna Pagh, Rasmus Pagh and Mikkel Thorup

The Average Case Analysis of Partition Sorts
Richard Cole, David C. Kandathil

Labeling Smart Dust
Vikas Bansal, Friedhelm Meyer auf der Heide and Christian Sohler

An inductive construction for plane Laman graphs via vertex splitting
Zsolt Fekete, Tibor Jordan and Walter Whiteley

Direct Routing: Algorithms and Complexity
Costas Busch, Malik Magdon-Ismail,  Marios Mavronicolas and Paul Spirakis

An Algorithm for Computing DNA Walks
Ankur Bhargava and S. Rao Kosaraju

Equivalence of Search Capability among Mobile Guards with Various Visibilities
Jae-Ha Lee, Sang-Min Park and Kyung-Yong Chwa


Engineering and Applications Track:

Code Flexibility and Program Efficiency by Genericity: Improving Cgal's Arrangements
Efi Fogel, Ron Wein, Dan Halperin

Load Balancing of Indivisible Unit Size Tokens in Dynamic and Heterogeneous Networks
Robert Elsaesser, Burkhard Monien, Stefan Schamberger

Computing with Real Algebraic Numbers of Small Degree
Ioannis Z. Emiris, Elias Tsigaridas

Beyond Optimal Play in Two-Person-Zerosum Games
Ulf Lorenz

Stable Minimum Storage Merging by Symmetric Comparisons
Pok-Son Kim, Arne Kutzner

Finding Dominators in Practice
Loukas Georgiadis, Renato F. Werneck, Robert E. Tarjan, Spyridon Triantafyllis, David August

Efficient IP Table Lookup via Adaptive Stratified Trees with Selective Reconstructions
Marco Pellegrini, Giordano Fusco

Construction of Minimum-Weight Spanners
Mikkel Sigurd, Martin Zachariasen

Solving Geometric Covering Problems by Data Reduction
Steffen Mecke, Dorothea Wagner

Classroom Examples of Robustness Problems in Geometric Computations
Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, Chee Yap

A Straight Skeleton Approximating the Medial Axis
Mirela Tanase, Remco C. Veltkamp

An Experimental Study of Random Knapsack Problems
Rene Beier, Berthold Voecking

Super Scalar Sample Sort
Peter Sanders, Sebastian Winkel

On Rectangular Cartograms
Marc van Kreveld, Bettina Speckmann

Contraction and Treewidth Lower Bounds
Hans L. Bodlaender, Arie M. C. A. Koster, Thomas Wolle

Multi-word Atomic Read/Write Registers on Multiprocessor Systems
Andreas Larsson, Anders Gidenstam, Phuong H. Ha, Marina Papatriantafilou, Philippas Tsigas

Data Migration on Parallel Disks
Leana Golubchik, Samir Khuller, Yoo-Ah Kim, Svetlana Shargorodskaya, Yung-Chun (Justin) Wan

Non-additive Shortest Paths
George Tsaggouris, Christos Zaroliagis