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

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