6. ESA 1998: Venice, Italy

Invited Lectures

• Jeffrey Scott Vitter:
  External Memory Algorithms. 1-25
  
• Eli Upfal:
  Design and Analysis of Dynamic Processes: A Stocastic Approach. 26-34
  

Data Structures

• Bernard Chazelle:
  Car-Pooling as a Data Structuring Device: The Soft Heap. 35-42
  
• Phillip G. Bradford, Mordecai J. Golin, Lawrence L. Larmore, Wojciech Rytter:
  Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property. 43-54
  
• Enrico Nardelli, Guido Proietti, Peter Widmayer:
  Finding All the Best Swaps of a Minimum Diameter Spanning Tree under Transient Edge Failures. 55-66
  

Strings and Biology

• Yossi Matias, S. Muthukrishnan, Süleyman Cenk Sahinalp, Jacob Ziv:
  Augmenting Suffix Trees, with Applications. 67-78
  
• Brenda S. Baker, Raffaele Giancarlo:
  Longest Common Subsequence from Fragments via Sparse Dynamic Programming. 79-90
  
• Philip N. Klein:
  Computing the Edit-Distance between Unrooted Ordered Trees. 91-102
  
• Michael R. Fellows, Michael T. Hallett, Chantal Korostensky, Ulrike Stege:
  Analogs and Duals of teh MAST Problem for Sequences and Trees. 103-114
  

Numerical Algorithms

• Felipe Cucker, Steve Smale:
  Complexity Estimates Depending on Condition and Round-Off Error. 115-126
  
• J. Maurice Rojas:
  Intrinsic Near Quadratic Complexity Bounds for Real Multivariate Root Counting. 127-138
  
• Arne Storjohann, Thom Mulders:
  Fast Algorithms for for Linear Algebra Modulo N. 139-150
  
• Johannes Blömer:
  A Probabilistic Zero-Test for Expressions Involving Root of Rational Numbers. 151-162
  

Geometry

• Matthias Fischer, Tamás Lukovszki, Martin Ziegler:
  Geometric Searching in Walkthrough Animations with Weak Spanners in Real Time. 163-174
  
• Fabrizio d'Amore, Paolo Giulio Franciosa, Giuseppe Liotta:
  Robust Region Approach to the Computation of Geometric Graphs (Extended Abstract). 175-186
  
• Stephan Eidenbenz, Christoph Stamm, Peter Widmayer:
  Positioning Guards at Fixed Height Above a Terrain - An Optimum Inapproximability Result. 187-198
  
• Chan-Su Shin, Jung-Hyun Kim, Sung Kwon Kim, Kyung-Yong Chwa:
  Two-Center Problems for a Convex Polygon (Extended Abstract). 199-210
  
• T. M. Murali, Pankaj K. Agarwal, Jeffrey Scott Vitter:
  Constructing Binary Space Partitions for Orthogonal Rectabgles in Practice. 211-222
  

Randomized and On-Line Algorithms

• Ravi Kannan, Andreas Nolte:
  A Fast Random Greedy Algorithm for the Component Commonality Problem. 223-234
  
• Bala Kalyanasundaram, Kirk Pruhs:
  Maximizing Job Completions Online. 235-246
  
• Yair Bartal, Marek Chrobak, Lawrence L. Larmore:
  A Randomized Algorithm for Two Servers on the Line (Extended Abstract). 247-258
  

Parallel and Distributed Algorithms I

• Petr Kolman:
  On Nonblocking Properties on the Benes Network. 259-270
  
• Piotr Berman, Juan A. Garay:
  Adaptability and the Usefulness of Hints (Extended Abstract). 271-282
  
• Evangelos Kranakis, Danny Krizanc, Andrzej Pelc:
  Fault-Tolerant Broadcasting in Radio Networks (Extended Abstract). 283-294
  
• Kazuo Iwama, Yahiko Kambayashi, Eiji Miyano:
  New Bounds for Oblivious Mesh Routing. 295-306
  
• Edith Cohen, Balachander Krishnamurthy, Jennifer Rexford:
  Evaluating Server-Assisted Cache Replacement in the Web. 307-319
  

Graph Algorithms

• Daniele Frigioni, Alberto Marchetti-Spaccamela, Umberto Nanni:
  Fully Dynamic Shortest Paths and Negative Cycles Detection on Digraphs with Arbitrary Arc Weights. 320-331
  
• James Abello, Adam L. Buchsbaum, Jeffery Westbrook:
  A Functional Approach to External Graph Algorithms. 332-343
  
• Vincent Bouchitté, Ioan Todinca:
  Minimal Triangulations for Graphs with "Few" Minimal Separators. 344-355
  
• Danny Z. Chen, Ovidiu Daescu, Xiaobo Hu, Jinhui Xu:
  Finding an Optimal Path without Growing the Tree. 356-367
  
• Daniele Frigioni, Tobias Miller, Umberto Nanni, Giulio Pasqualone, Guido Schäfer, Christos D. Zaroliagis:
  An Experimental Study of Dynamic Algorithms for Directed Graphs. 368-380
  
• Robert W. Irving:
  Matching Medical Students to Pairs of Hospitals: A New Variation on a Well-Known Theme. 381-392
  

Parallel and Distributed Algorithms II

• Ulrich Meyer, Peter Sanders:
  Delta-Stepping: A Parallel Single Source Shortest Path Algorithm. 393-404
  
• Ka Wong Chong, Edgar A. Ramos:
  Improved Deterministic Parallel Padded Sorting. 405-416
  
• Micah Adler, Petra Berenbrink, Klaus Schröder:
  Analyzing an Infinite Parallel Job Allocation Process. 417-428
  
• Ralf Diekmann, Andreas Frommer, Burkhard Monien:
  Nearest Neighbor Load Balancing on Graphs. 429-440
  

Optimization

• Roberto Solis-Oba:
  2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves. 441-452
  
• Christopher S. Helvig, Gabriel Robins, Alexander Zelikovsky:
  Moving-Target TSP and Related Problems. 453-464
  
• Johan Håstad, Lars Ivansson, Jens Lagergren:
  Fitting Points on the Real Line and Its Application to RH Mapping. 465-476
  
• Michael Krivelevich, Benny Sudakov:
  Approximate Coloring of Uniform Hypergraphs (Extended Abstract). 477-489
  
• Daniel W. Engels, David R. Karger, Stavros G. Kolliopoulos, Sudipta Sengupta, R. N. Uma, Joel Wein:
  Techniques for Scheduling with Rejection. 490-501
  
• Sergey V. Sevastianov, I. D. Tchernykh:
  Computer-Aided Way to Prove Theorems in Scheduling. 502-513