ESA 2002
10th European Symposium on Algorithms

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

Page maintained by Camil Demetrescu