Algorithmica, Volume 14, 1995

Volume 14, Number 1, July 1995

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

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

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

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 BibTeX
Samir Khuller, Balaji Raghavachari, Neal E. Young: Balancing Minimum Spanning Trees and Shortest-Path Trees. 305-321 BibTeX
Sairam Subramanian, Roberto Tamassia, Jeffrey Scott Vitter: An Efficient Parallel Algorithm for Shortest Paths in Planar Layered Digraphs. 322-339 BibTeX
Wolfgang Panny, Helmut Prodinger: Bottom-Up Mergesort - a Detailed Analysis. 340-354 BibTeX
Dany Breslauer, Zvi Galil: Finding All Periods and Initial Palindromes of a String in Parallel. 355-366 BibTeX

Yui-Bin Chen, Doug Ierardi: The Complexity of Oblivious Plans for Orienting and Distinguishing Polygonal Parts. 367-397 BibTeX
Ming-Yang Kao, Shang-Hua Teng, Kentaro Toyama: An Optimal Parallel Algorithm for Planar Cycle Separators. 398-408 BibTeX
Andrew Chi-Chih Yao: Minimean Optimal Key Arrangements in Hash Tables. 409-428 BibTeX
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 BibTeX

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