List of accepted papers for ESA 2002: Design and Anylysis Track: Finding The Sink Takes Some Time Ingo Schurr and Tibor Szabo Time-Expanded Graphs with Flow-Dependent Transit Times Ekkehard Koehler, Katharina Langkau, and Martin Skutella Truthful and Competitive Market Clearing Kaustubh Deshmukh, Jason Hartline, Andrew Goldberg, and Anna Karlin Minimizing Makespan and Preemption Costs on a System of Uniform Machines Hadas Shachnai, Tami Tamir, and Gerhard J. Woeginger On the k-splittable flow problem Georg Baier, Ekkehard Koehler, and Martin Skutella Approximation algorithms for k-line center Pankaj K Agarwal, Cecilia M Procopiuc, and Kasturi Varadarajan Three-Dimensional Layers of Maxima Adam L. Buchsbaum and Michael T. Goodrich A Primal Approach to the Stable Set Problem Claudio Gentile, Utz-Uwe Haus, Matthias Koeppe, Giovanni Rinaldi, and Robert Weismantel 1.375-Approximation Algorithm for Sorting by Reversals Piotr Berman, Sridhar Hannenhalli, and Marek Karpinski A Comparison of Multicast Pull Models Kirk Pruhs and Patchrawat Uthaisombut Approximating medial axis from the Voronoi diagram with convergence Tamal K. Dey and Wulue Zhao Online Companion Caching Amos Fiat, Manor Mendel, and Steve Seiden Constructing plane spanners of bounded degree and low weight Prosenjit Bose, Joachim Gudmundsson, and Michiel Smid External-Memory Breadth-First Search with Sublinear I/O Kurt Mehlhorn and Ulrich Meyer Efficient Constructions of Generalized Superimposed Codes with Applications to Group Testing and Conflict Resolution in Multiple Access Channels Annalisa De Bonis and Ugo Vaccaro Partial alphabetic trees Arye Barkan and Haim Kaplan Vector assignment problems: A general framework Leah Epstein and Tamir Tassa 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 Radio labeling with pre-assigned frequencies HL Bodlaender, HJ Broersma, FV Fomin, AV Pyatkin, and GJ Woeginger A simple linear time algorithm for finding even triangulations of 2-connected bipartite plane graphs Huaming Zhang and Xin He Scheduling malleable parallel tasks: an asymptotic fully polynomial-time approximation scheme Klaus Jansen Minimizing the maximum starting time on-line Leah Epstein and Rob van Stee Range Searching in Categorical Data: Colored Range Searching on Grid Pankaj K. Agarwal and Sathish Govindarajan and S. Muthukrishnan Deterministic Communication in Radio Networks with Large Labels Leszek Gasieniec, Aris Pagourtzis, and Igor Potapov 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 problem for cubic graphs Krzysztof Lorys and Grazyna Zwozniak Covering Things with Things Stefan Langerman and Pat Morin Engineering and Applications Track: A fast, accurate and simple method for pricing European-Asian option and Saving-Asian option K. Ohta, K. Sadakane, A. Shioura, T. Tokuyama Real-Time Dispatching of Guided and Unguided Automobile Service Units with Soft Time Windows Sven O. Krumke, Joerg Rambau, Luis M. Torres Speeding Up the Incremental Construction of the Union of Triangles Eti Ezra, Dan Halperin and Micha Sharir An Exact Algorithm for the Uniformly-Oriented Steiner Tree Problem Benny K. Nielsen and Pawel Winter and Martin Zachariasen Extending Reducion Techniques for the Steiner Tree Problem Tobias Polzin High-Level Filtering for Arrangements of Conic Arcs Ron Wein Geometric Algorithms for Density-Based Data Clustering Danny X. Chen and Michiel Smid and Bin Xu Efficient Implementation of a Minimal Triangulation Algorithm Pinar Heggernes and Yngve Villanger Sorting 13 Elements Requires 34 Comparisons Marcin Peczarski A Software Library for Elliptic Curve Cryptography Elisavet Konstantinou and Yiannis Stamatiou and Christos Zaroliagis New Heuristics and Lower Bounds for the Min-Max k-Chinese Postman Dino Ahr and Gerhard Reinelt Experiments with lightweight suffix array construction algorithms P. Ferragina and G. Manzini Capacitated Network Design - Cardinality Cuts and Coupled Variable Fixing Algorithms Meinolf Sellmann and Georg Kliewer and Achim Koberstein Implementing I/O-Efficient Data Structures Using TPIE Lars Arge and Octavian Procopiuc and Jeffrey Scott Vitter 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 Design and Implementation of Efficient Data Types for Static Graphs Stefan Naeher and Oliver Zlotowski SCIL - Symbolic Constraints in Integer Linear Programming Ernst Althaus and Alexander Bockmayr and Matthias Elf and Thomas Simple and Fast: Improving a Branch\&Bound Algorithm for Maximum Clique Torsten Fahle Optimal Terrain Construction Problems and Applications in Danny Z. Chen and Xiaobo S. Hu and Shuang Luan and Xiaodong Wu 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 An experimental analysis of shortest path and routing Chris Barrett and Keith Bissett and Rico Jacob and Goran Konjevod Two Simplified Algorithms for Maintaining Order in a List Michael A. Bender and Richard Cole and Erik D. Demaine and Martin Farach-Colton Determining similarity of Conformational Polymorphs Angela Enosh and Klara Kedem and Joel Bernstein 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