Algorithmica, Volume 5, 1990

Volume 5, Number 1, 1990

Benny Chor, Oded Goldreich: An Improved Parallel Algorithm for Integer GCD. 1-10
Teofilo F. Gonzalez, Si-Qing Zheng: Approximation Algorithms for Partitioning a Rectangle with Interior Points. 11-42
Clyde P. Kruskal, Larry Rudolph, Marc Snir: Efficient Parallel Algorithms for Graph Problems. 43-64
M. Orlowski: A New Algorithm for the Largest Empty Rectangle Problem. 65-73
Mike Paterson: Improved Sorting Networks with O(log N) Depth. 65-92
Daniel Bienstock, Clyde L. Monma: On the Complexity of Embedding Planar Graphs To Minimize Certain Distance Measures. 93-109
Ding-Zhu Du, Yanjun Zhang: On Heuristics for Minimum Length Rectilinear Partitions. 111-128
Xin He, Yaacov Yesha: Efficient Parallel Algorithms for r-Dominating Set and p-Center Problems on Trees. 129-145

Shang-Ching Chou, William F. Schelter, Jin-Gen Yang: An Algorithm for Constructing Gröbner Bases from Characteristic Sets and Its Application to Geometry. 147-154
C. S. Jeong, D. T. Lee: Parallel Geometric Algorithms on a Mesh-Connected Computer. 155-177
Carla D. Savage, Matthias F. M. Stallmann, Jo Ellen Perry: Solving Some Combinatorial Problems on Arrays with One-Way Dataflow. 179-199
S. Sudarshan, C. Pandu Rangan: A Fast Algorithm for Computing Sparse Visibility Graphs. 210-214
Kurt Mehlhorn, Stefan Näher: Dynamic Fractional Cascading. 215-241
Ian Parberry: An Optimal Time Bound for Oblivious Routing. 243-250
Gabriele Blankenagel, Ralf Hartmut Güting: Internal and External Algorithms for the Points-in-Regions Problem-the INSIDE Join of Geo-Relational Algebra. 251-276
Israel Cidon, Inder S. Gopal: Dynamic Detection of Subgraphs in Computer Networks. 277-294

Joseph C. Culberson, J. Ian Munro: Analysis of the Standard Deletion Algorithms in Exact Fit Domain Binary Search Trees. 295-311
Esko Ukkonen: A Linear-Time Algorithm for Finding Approximate Shortest Common Superstrings. 313-323
Friedemann Mattern: Asynchronous Distributed Termination-Parallel and Symmetric Solutions with Echo Algorithms. 325-340
Ming-Tat Ko, Richard C. T. Lee, Jyun-Sheng Chang: An Optimal Approximation Algorithm for the Rectilinear m-Center Problem. 341-352
Bruce Randall Donald: The Complexity of Planar Compliant Motion Planning Under Uncertainty. 353-382
Michael M. Wu, Michael C. Loui: An Efficient Distributed Algorithm for Maximum Matching in General Graphs. 383-406
Clyde L. Monma, Mike Paterson, Subhash Suri, F. Frances Yao: Computing Euclidean Maximum Spanning Trees. 407-419
David P. Dobkin, Diane L. Souvaine: Computational Geometry in a Curved World. 421-457
Bonnie Berger, John Rompel: A Better Performance Guarantee for Approximate Graph Coloring. 459-466

Yen-Tai Lai, Sany M. Leinwand: A Theory of Rectangular Dual Graphs. 467-483
Sang Ho Lee, Kyung-Yong Chwa: Some Chain Visibility Problems in a Simple Polygon. 485-507
Roberto Tamassia, Franco P. Preparata: Dynamic Maintenance of Planar Digraphs, with Applications. 509-527
Fabrizio Luccio, Andrea Pietracaprina, Geppino Pucci: A New Scheme for the Deterministic Simulation of PRAMs in VLSI. 529-544
Xin He: Efficient Parallel and Sequential Algorithms for 4-Coloring Perfect Planar Graphs. 545-559
David P. Dobkin, Herbert Edelsbrunner, Mark H. Overmars: Searching for Empty Convex Polygons. 561-571
Panagiotis Alevizos, Jean-Daniel Boissonnat, Franco P. Preparata: An Optimal Algorithm for the Boundary of a Cell in a Union of Rays. 573-590
Frank K. Hwang, Y. C. Yao: Comments on Bern's Probabilistic Results on Rectilinear Steiner Trees. 591-598