Accepted papers
Design and Analysis track	Engineering and Applications track
Finding The Sink Takes Some Time Ingo Schurr and Tibor Szabo	A fast, accurate and simple method for pricing European-Asian option and Saving-Asian option K. Ohta, K. Sadakane, A. Shioura, T. Tokuyama
Time-Expanded Graphs with Flow-Dependent Transit Times Ekkehard Koehler, Katharina Langkau, and Martin Skutella	Real-Time Dispatching of Guided and Unguided Automobile Service Units with Soft Time Windows Sven O. Krumke, Joerg Rambau, Luis M. Torres
Truthful and Competitive Market Clearing Kaustubh Deshmukh, Jason Hartline, Andrew Goldberg, and Anna Karlin	Speeding Up the Incremental Construction of the Union of Triangles Eti Ezra, Dan Halperin and Micha Sharir
Minimizing Makespan and Preemption Costs on a System of Uniform Machines Hadas Shachnai, Tami Tamir, and Gerhard J. Woeginger	An Exact Algorithm for the Uniformly-Oriented Steiner Tree Problem Benny K. Nielsen and Pawel Winter and Martin Zachariasen
On the k-splittable flow problem Georg Baier, Ekkehard Koehler, and Martin Skutella	Extending Reduction Techniques for the Steiner Tree Problem Tobias Polzin and Siavash Vahdati Daneshmand
Approximation algorithms for k-line center Pankaj K Agarwal, Cecilia M Procopiuc, and Kasturi Varadarajan	High-Level Filtering for Arrangements of Conic Arcs Ron Wein
Three-Dimensional Layers of Maxima Adam L. Buchsbaum and Michael T. Goodrich	Geometric Algorithms for Density-Based Data Clustering Danny X. Chen and Michiel Smid and Bin Xu
A Primal Approach to the Stable Set Problem Claudio Gentile, Utz-Uwe Haus, Matthias Koeppe, Giovanni Rinaldi, and Robert Weismantel	Efficient Implementation of a Minimal Triangulation Algorithm Pinar Heggernes and Yngve Villanger
1.375-Approximation Algorithm for Sorting by Reversals Piotr Berman, Sridhar Hannenhalli, and Marek Karpinski	Sorting 13 Elements Requires 34 Comparisons Marcin Peczarski
A Comparison of Multicast Pull Models Kirk Pruhs and Patchrawat Uthaisombut	A Software Library for Elliptic Curve Cryptography Elisavet Konstantinou and Yiannis Stamatiou and Christos Zaroliagis
Approximating medial axis from the Voronoi diagram with convergence Tamal K. Dey and Wulue Zhao	New Heuristics and Lower Bounds for the Min-Max k-Chinese Postman Dino Ahr and Gerhard Reinelt
Online Companion Caching Amos Fiat, Manor Mendel, and Steve Seiden	Experiments with lightweight suffix array construction algorithms P. Ferragina and G. Manzini
Constructing plane spanners of bounded degree and low weight Prosenjit Bose, Joachim Gudmundsson, and Michiel Smid	Capacitated Network Design - Cardinality Cuts and Coupled Variable Fixing Algorithms Meinolf Sellmann and Georg Kliewer and Achim Koberstein
External-Memory Breadth-First Search with Sublinear I/O Kurt Mehlhorn and Ulrich Meyer	Implementing I/O-Efficient Data Structures Using TPIE Lars Arge and Octavian Procopiuc and Jeffrey Scott Vitter
Efficient Constructions of Generalized Superimposed Codes with Applications to Group Testing and Conflict Resolution in Multiple Access Channels Annalisa De Bonis and Ugo Vaccaro	A Computational Basis for Conic Arcs and Boolean Operations on Conic Polygons Eric Berberich and Arno Eigenwillig and Michael Hemmer and Susan Hert and Kurt Mehlhorn and Elmar Schoemer
Partial alphabetic trees Arye Barkan and Haim Kaplan	Design and Implementation of Efficient Data Types for Static Graphs Stefan Naeher and Oliver Zlotowski
Vector assignment problems: A general framework Leah Epstein and Tamir Tassa	SCIL - Symbolic Constraints in Integer Linear Programming Ernst Althaus and Alexander Bockmayr and Matthias Elf and Thomas
TSP with Neighborhoods of Varying Size Mark de Berg, Joachim Gudmundsson, Matthew J. Katz, Christos Levcopoulos, Mark H. Overmars and A. Frank van der Stappen	Simple and Fast: Improving a Branch&Bound Algorithm for Maximum Clique Torsten Fahle
Radio labeling with pre-assigned frequencies HL Bodlaender, HJ Broersma, FV Fomin, AV Pyatkin, and GJ Woeginger	Optimal Terrain Construction Problems and Applications in Danny Z. Chen and Xiaobo S. Hu and Shuang Luan and Xiaodong Wu
A simple linear time algorithm for finding even triangulations of 2-connected bipartite plane graphs Huaming Zhang and Xin He	Near-linear time approximation algorithms for curve simplification in two and three dimensions Pankaj K. Agarwal and Sariel Har-Peled and Nabil H. Mustafa and Yusu Wang
Scheduling malleable parallel tasks: an asymptotic fully polynomial-time approximation scheme Klaus Jansen	An experimental analysis of shortest path and routing Chris Barrett and Keith Bissett and Rico Jacob and Goran Konjevod
Minimizing the maximum starting time on-line Leah Epstein and Rob van Stee	Two Simplified Algorithms for Maintaining Order in a List Michael A. Bender and Richard Cole and Erik D. Demaine and Martin Farach-Colton
Range Searching in Categorical Data: Colored Range Searching on Grid Pankaj K. Agarwal and Sathish Govindarajan and S. Muthukrishnan	Determining similarity of Conformational Polymorphs Angela Enosh and Klara Kedem and Joel Bernstein
Deterministic Communication in Radio Networks with Large Labels Leszek Gasieniec, Aris Pagourtzis, and Igor Potapov	Branch and bound algorithms for the minimum test set problem K.M.J. de Bontridder and J.K.Lenstra and J.B. Orlin and L. Stougie
Minimizing the total completion time on a single on-line machine, using restarts Rob van Stee and Han La Poutre
Wide-sense Nonblocking WDM Cross-connects Penny Haxell, April Rasala, Gordon Wilfong, and Peter Winkler
An approximation scheme for cake division with a linear number of cuts Gerhard J. Woeginger
Translating a Planar Object to Maximize Point Containment Pankaj K. Agarwal, Torben Hagerup, Rahul Ray, Micha Sharir, Michiel Smid, and Emo Welzl
Estimating Rarity and Similarity over Data Stream Windows Mayur D. Datar and S. Muthukrishnan
Butterflies and Peer-to-Peer Networks Mayur D. Datar
Online Scheduling for Sorting Buffers Harald Raecke, Christian Sohler, and Matthias Westermann
Frequency Estimation of Internet Packet Streams with Limited Space Erik D. Demaine, Alejandro Lopez-Ortiz, and J. Ian Munro
Balanced-replication algorithms for distribution trees Edith Cohen and Haim Kaplan
On-line dial-a-ride problems under a restricted information model M. Lipmann, X. Lu, W.E. de Paepe, R.A. Sitters and L. Stougie
Partially-Ordered Knapsack and Applications to Scheduling Stavros G. Kolliopoulos and George Steiner
Computing the Planar Additively Weighted Voronoi diagram Dynamically Menelaos I. Karavelas and Mariette Yvinec
Non-independent Randomized Rounding and an Application to Digital Halftoning Benjamin Doerr and Henning Schnieder
Optimal graph exploration without good maps Anders Dessmark and Andrzej Pelc
Randomized Results for Query Optimization Problems on Two Processors Eduardo Laber, Ojas Parekh, and R. Ravi
Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy Michael A. Bender, Richard Cole, Erik D. Demaine, and Martin Farach-Colton
Computing Homotopic Shortest Paths Efficiently Alon Efrat, Stephen G. Kobourov, and Anna Lubiw
Complexity of compatible decompositions of eulerian graphs and their transformations Jana Maxova and Jaroslav Nesetril
Frequency Channel Assignment on Planar Networks Michael Molloy and Mohammad R. Salavatipour
Efficient Tree Layout in a Multilevel Memory Hierarchy Michael A. Bender, Erik D. Demaine, and Martin Farach-Colton
Eager st-Ordering Ulrik Brandes
Kinetic Medians and kd-Trees Pankaj K. Agarwal, Jie Gao, and Leonidas J. Guibas
The probabilistic analysis of a greedy satisfiability algorithm Alexis C. Kaporis, Lefteris M. Kirousis, and Efthimios G. Lalas
An Algorithm for Dualization in Products of Lattices Khaled Elbassioni
Approximation algorithm for the maximum leaf spanning tree problem for cubic graphs Krzysztof Lorys and Grazyna Zwozniak
Covering Things with Things Stefan Langerman and Pat Morin