Algorithmica, Volume 20, 1998

Volume 20, Number 1, January 1998

• Anne Condon, Lata Narayanan: Upper and Lower Bounds for Selection in the Mesh. 1-30
• David Alberts, Monika Rauch Henzinger: Average-Case Analysis of Dynamic Graph Algorithms. 31-60
• Franz Aurenhammer, F. Hoffmann, Boris Aronov: Minkowski-Type Theorems and Least-Squares Clustering. 61-76
• Nader H. Bshouty, Christino Tamon, David K. Wilson: On Learning Decision Trees with Large Output Domains. 77-100
• Joseph Y.-T. Leung, Tommy W. Tam, C. S. Wong, Gilbert H. Young: Minimizing Mean Flow Time with Error Constraint. 101-118

Volume 20, Number 2, February 1998

• David Harel, Meir Sardas: An Algorithm for Straight-Line Drawing of Planar Graphs. 119-135
• Jirí Matousek, David M. Mount, Nathan S. Netanyahu: Efficient Randomized Algorithms for the Repeated Median Line Estimator. 136-150
• Guy Even, Joseph Naor, Baruch Schieber, Madhu Sudan: Approximating Minimum Feedback Sets and Multicuts in Directed Graphs. 151-174
• Eric Torng: A Unified Analysis of Paging and Caching. 175-200
• Dae Seoung Kim, Kwan-Hee Yoo, Kyung-Yong Chwa, Sung Yong Shin: Efficient Algorithms for Computing a Complete Visibility Region in Three-Dimensional Space. 201-225

Volume 20, Number 3, March 1998

• Kwan-Hee Yoo, Dae Seoung Kim, Sung Yong Shin, Kyung-Yong Chwa: Linear-Time Algorithms for Finding the Shadow Volumes from a Convex Area Light Source. 227-241
• Yefim Dinitz, Jeffery Westbrook: Maintaining the Classes of 4-Edge-Connectivity in a Graph On-Line. 242-276
• A. Gräf, M. Stumpf, Gerhard Weißenfels: On Coloring Unit Disk Graphs. 277-293
• Siu-Wing Cheng, Michael Kaminski, Shmuel Zaks: Minimum Dominating Sets of Intervals on Lines. 294-308
• Tadao Takaoka: Subcubic Cost Algorithms for the All Pairs Shortest Path Problem. 309-318

Volume 20, Number 4, April 1998

• Evanthia Papadopoulou, D. T. Lee: A New Approach for the Geodesic Voronoi Diagram of Points in a Simple Polygon and Other Restricted Polygonal Domains. 319-352
• Maxime Crochemore, Costas S. Iliopoulos, Maureen Korda: Two-Dimensional Prefix String Matching and Covering on Square Matrices. 353-373
• Sudipto Guha, Samir Khuller:
  Approximation Algorithms for Connected Dominating Sets. 374-387
  
• Martin Farach, Mikkel Thorup: String Matching in Lempel-Ziv Compressed Strings. 388-404