Algorithmica, Volume 14, 1995

Volume 14, Number 1, July 1995

Sven Schuierer, Derick Wood: Staircase Visibility and Computation of Kernels. 1-26
Seung-Hak Choi, Sung Yong Shin, Kyung-Yong Chwa: Characterizing and Recognizing the Visibility Graph of a Funnel-Shaped Polygon. 27-51
Bogdan S. Chlebus, Krzysztof Diks, Miroslaw Kowaluk: O(log log n)-Time Integer Geometry on the CRCW PRAM. 52-69
Sally A. Goldman, Robert H. Sloan: Can PAC Learning Algorithms Tolerate Random Attribute Noise? 70-84
James R. Knight, Eugene W. Myers: Approximate Regular Expression Pattern Matching with Concave Gap Penalties. 85-121

Richard B. Borie: Generation of Polynomial-Time Algorithms for Some Optimization Problems on Tree-Decomposable Graphs. 123-137
Leizhen Cai, Derek G. Corneil: Isomorphic Tree Spanner Problems. 138-153
Paul F. Dietz, Kurt Mehlhorn, Rajeev Raman, Christian Uhrig: Lower Bounds for Set Intersection Queries. 154-168
Nancy M. Amato, Franco P. Preparata: A Time-Optimal Parallel Algorithm for Three-Dimensional Convex Hulls. 169-182
Nancy M. Amato: Finding a Closest Visible Vertex Pair Between Two Polygons. 183-201

Shuo-Yan Chou, R. C. Woo: A Linear-Time Algorithm for Constructing a Circular Visibility Diagram. 203-228
Ross M. McConnell: An O(n²) Incremental Algorithm for Modular Decomposition of Graphs and 2-Structures. 229-248
Esko Ukkonen: On-Line Construction of Suffix Trees. 249-260
Andrzej Lingas, Anil Maheshwari, Jörg-Rüdiger Sack: Optimal Parallel Algorithms for Rectilinear Link-Distance Problems. 261-289

Frank Thomson Leighton, Fillia Makedon, Ioannis G. Tollis: A 2n-2 Step Algorithm for Routing in an n*n Array with Constant-Size Queues. 291-304
Samir Khuller, Balaji Raghavachari, Neal E. Young: Balancing Minimum Spanning Trees and Shortest-Path Trees. 305-321
Sairam Subramanian, Roberto Tamassia, Jeffrey Scott Vitter: An Efficient Parallel Algorithm for Shortest Paths in Planar Layered Digraphs. 322-339
Wolfgang Panny, Helmut Prodinger: Bottom-Up Mergesort - a Detailed Analysis. 340-354
Dany Breslauer, Zvi Galil: Finding All Periods and Initial Palindromes of a String in Parallel. 355-366

Yui-Bin Chen, Doug Ierardi: The Complexity of Oblivious Plans for Orienting and Distinguishing Polygonal Parts. 367-397
Ming-Yang Kao, Shang-Hua Teng, Kentaro Toyama: An Optimal Parallel Algorithm for Planar Cycle Separators. 398-408
Andrew Chi-Chih Yao: Minimean Optimal Key Arrangements in Hash Tables. 409-428
Mikhail J. Atallah, Danny Z. Chen, D. T. Lee: An Optimal Algorithm for Shortest Paths on Weighted Interval and Circular-Arc Graphs, with Applications. 429-441

Bruce Randall Donald, Patrick G. Xavier: Provably Good Approximation Algorithms for Optimal Kinodynamic Planning: Robots with Decoupled Dynamics Bounds. 443-479
Bruce Randall Donald, Patrick G. Xavier: Provably Good Approximation Algorithms for Optimal Kinodynamic Planning for Cartesian Robots and Open-Chain Manipulators. 480-530