Front matter
1
External Memory Algorithms
Jeffrey Scott Vitter
1
Design and Analysis of Dynamic Processes: A Stochastic Approach (Invited Paper)
Eli Upfal
1
Car-Pooling as a Data Structuring Device: The Soft Heap
Bernard Chazelle
1
Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property
Phil Bradford, Mordecai J. Golin, Lawrence L. Larmore and Wojciech Rytter
1
Finding All the Best Swaps of a Minimum Diameter Spanning Tree Under Transient Edge Failures
Enrico Nardelli, Guido Proietti and Peter Widmayer
1
Augmenting Suffix Trees, with Applications
Yossi Matias, S. Muthukrishnan, Süleyman Cenk Sahinalp and Jacob Ziv
1
Longest Common Subsequence from Fragments via Sparse Dynamic Programming
Brenda S. Baker and Raffaele Giancarlo
1
Computing the Edit-Distance Between Unrooted Ordered Trees
Philip N. Klein
1
Analogs and Duals of the MAST Problem for Sequences and Trees
Michael Fellows, Michael Hallett, Chantal Korostensky and Ulrike Stege
1
Complexity Estimates Depending on Condition and Round-Off Error
Felipe Cucker and Steve Smale
1
Intrinsic Near Quadratic Complexity Bounds for Real Multivariate Root Counting
J. Maurice Rojas
1
Fast Algorithms for Linear Algebra Modulo
N
Arne Storjohann and Thom Mulders
1
A Probabilistic Zero-Test for Expressions Involving Roots of Rational Numbers
Johannes Blömer
1
Geometric Searching in Walkthrough Animations with Weak Spanners in Real Time
Matthias Fischer, Tamás Lukovszki and Martin Ziegler
1
A Robust Region Approach to the Computation of Geometric Graphs (Extended Abstract)
Fabrizio d’Amore, Paolo G. Franciosa and Giuseppe Liotta
1
Positioning Guards at Fixed Height Above a Terrain — An Optimum Inapproximability Result
Stephan Eidenbenz, Christoph Stamm and Peter Widmayer
1
Two-Center Problems for a Convex Polygon (Extended Abstract)
Chan-Su Shin, Jung-Hyun Kim, Sung Kwon Kim and Kyung-Yong Chwa
1
Constructing Binary Space Partitions for Orthogonal Rectangles in Practice
T. M. Murali, Pankaj K. Agarwal and Jeffrey Scott Vitter
1
A Fast Random Greedy Algorithm for the Component Commonality Problem
Ravi Kannan and Andreas Nolte
1
Maximizing Job Completions Online
Bala Kalyanasundaram and Kirk Pruhs
1
A Randomized Algorithm for Two Servers on the Line (Extended Abstract)
Yair Bartal, Marek Chrobak and Lawrence L. Larmore
1
On Nonblocking Properties of the Beneš Network
Petr Kolman
1
Adaptability and the Usefulness of Hints (Extended Abstract)
Piotr Berman and Juan A. Garay
1
Fault-Tolerant Broadcasting in Radio Networks (Extended Abstract)
Evangelos Kranakis, Danny Krizanc and Andrzej Pelc
1
New Bounds for Oblivious Mesh Routing
Kazuo Iwama, Yahiko Kambayashi and Eiji Miyano
1
Evaluating Server-Assisted Cache Replacement in the Web
Edith Cohen, Balachander Krishnamurthy and Jennifer Rexford
1
Fully Dynamic Shortest Paths and Negative Cycles Detection on Digraphs with Arbitrary Arc Weights
D. Frigioni, A. Marchetti-Spaccamela and U. Nanni
1
A Functional Approach to External Graph Algorithms
James Abello, Adam L. Buchsbaum and Jeffery R. Westbrook
1
Minimal Triangulations for Graphs with “Few” Minimal Separators
Vincent Bouchitté and Ioan Todinca
1
Finding an Optimal Path without Growing the Tree
Danny Z. Chen, Ovidiu Daescu, Xiaobo (Sharon) Hu and Jinhui Xu
1
An Experimental Study of Dynamic Algorithms for Directed Graphs
Daniele Frigioni, Tobias Miller, Umberto Nanni, Giulio Pasqualone and Guido Schaefer, et al.
1
Matching Medical Students to Pairs of Hospitals: A New Variation on a Well-known Theme
Robert W. Irving
1
Δ-Stepping : A Parallel Single Source Shortest Path Algorithm
Ulrich Meyer and Peter Sanders
1
Improved Deterministic Parallel Padded Sorting
Ka Wong Chong and Edgar A. Ramos
1
Analyzing an Infinite Parallel Job Allocation Process
Micah Adler, Petra Berenbrink and Klaus Schröder
1
Nearest Neighbor Load Balancing on Graphs
Ralf Diekmann, Andreas Frommer and Burkhard Monien
1
2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves
Roberto Solis-Oba
1
Moving-Target TSP and Related Problems
C. S. Helvig, Gabriel Robins and Alex Zelikovsky
1
Fitting Points on the Real Line and Its Application to RH Mapping
Johan Håstad, Lars Ivansson and Jens Lagergren
1
Approximate Coloring of Uniform Hypergraphs (Extended Abstract)
Michael Krivelevich and Benny Sudakov
1
Techniques for Scheduling with Rejection
Daniel W. Engels, David R. Karger, Stavros G. Kolliopoulos, Sudipta Sengupta and R. N. Uma, et al.
1
Computer-Aided Way to Prove Theorems in Scheduling
S. V. Sevastianov and I. D. Tchernykh
Back matter