Algorithms — ESA’ 98: 6th Annual European Symposium Venice, Italy, August 24–26, 1998 Proceedings

Jeffrey Scott Vitter (auth.), Gianfranco Bilardi, Giuseppe F. Italiano, Andrea Pietracaprina, Geppino Pucci (eds.)3540648488, 9783540648482

This book constitutes the refereed proceedings of the 6th Annual European Symposium on Algorithms, ESA’97, held in Venice, Italy, in August 1998.
The 40 revised full papers presented together with two invited contributions were carefully reviewed and selected from a total of 131 submissions. The book is divided into sections on data structures, strings and biology, numerical algorithms, geometry, randomized and online algorithms, parallel and distributed algorithms, graph algorithms, and optimization.

---

Table of contents :
External Memory Algorithms….Pages 1-25
Design and Analysis of Dynamic Processes: A Stochastic Approach (Invited Paper)….Pages 26-34
Car-Pooling as a Data Structuring Device: The Soft Heap….Pages 35-42
Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property….Pages 43-54
Finding All the Best Swaps of a Minimum Diameter Spanning Tree Under Transient Edge Failures….Pages 55-66
Augmenting Suffix Trees, with Applications….Pages 67-78
Longest Common Subsequence from Fragments via Sparse Dynamic Programming….Pages 79-90
Computing the Edit-Distance Between Unrooted Ordered Trees….Pages 91-102
Analogs and Duals of the MAST Problem for Sequences and Trees….Pages 103-114
Complexity Estimates Depending on Condition and Round-Off Error….Pages 115-126
Intrinsic Near Quadratic Complexity Bounds for Real Multivariate Root Counting….Pages 127-138
Fast Algorithms for Linear Algebra Modulo N ….Pages 139-150
A Probabilistic Zero-Test for Expressions Involving Roots of Rational Numbers….Pages 151-162
Geometric Searching in Walkthrough Animations with Weak Spanners in Real Time….Pages 163-174
A Robust Region Approach to the Computation of Geometric Graphs (Extended Abstract)….Pages 175-186
Positioning Guards at Fixed Height Above a Terrain — An Optimum Inapproximability Result….Pages 187-198
Two-Center Problems for a Convex Polygon (Extended Abstract)….Pages 199-210
Constructing Binary Space Partitions for Orthogonal Rectangles in Practice….Pages 211-222
A Fast Random Greedy Algorithm for the Component Commonality Problem….Pages 223-234
Maximizing Job Completions Online….Pages 235-246
A Randomized Algorithm for Two Servers on the Line (Extended Abstract)….Pages 247-258
On Nonblocking Properties of the Beneš Network….Pages 259-270
Adaptability and the Usefulness of Hints (Extended Abstract)….Pages 271-282
Fault-Tolerant Broadcasting in Radio Networks (Extended Abstract)….Pages 283-294
New Bounds for Oblivious Mesh Routing….Pages 295-306
Evaluating Server-Assisted Cache Replacement in the Web….Pages 307-319
Fully Dynamic Shortest Paths and Negative Cycles Detection on Digraphs with Arbitrary Arc Weights….Pages 320-331
A Functional Approach to External Graph Algorithms….Pages 332-343
Minimal Triangulations for Graphs with “Few” Minimal Separators….Pages 344-355
Finding an Optimal Path without Growing the Tree….Pages 356-367
An Experimental Study of Dynamic Algorithms for Directed Graphs….Pages 368-380
Matching Medical Students to Pairs of Hospitals: A New Variation on a Well-known Theme….Pages 381-392
Δ -Stepping : A Parallel Single Source Shortest Path Algorithm….Pages 393-404
Improved Deterministic Parallel Padded Sorting….Pages 405-416
Analyzing an Infinite Parallel Job Allocation Process….Pages 417-428
Nearest Neighbor Load Balancing on Graphs….Pages 429-440
2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves….Pages 441-452
Moving-Target TSP and Related Problems….Pages 453-464
Fitting Points on the Real Line and Its Application to RH Mapping….Pages 465-476
Approximate Coloring of Uniform Hypergraphs (Extended Abstract)….Pages 477-489
Techniques for Scheduling with Rejection….Pages 490-501
Computer-Aided Way to Prove Theorems in Scheduling….Pages 502-513