ACCEPTED PAPERS OF ESA 2004
Track A:
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
Dictionaries
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 a Class of 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
Track B:
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