Algorithmica, Volume 17, 1997

Volume 17, Number 1, January 1997

Theodore H. Romer, Louis E. Rosier: An Algorithm Reminiscent of Euclidean-gcd Computing a Function Related to Pinwheel Scheduling. 1-10 BibTeX
Brandon Dixon, Robert Endre Tarjan: Optimal Parallel Verification of Minimum Spanning Trees in Logarithmic Time. 11-18 BibTeX
Frank K. H. A. Dehne, Rolf Klein: "The Big Sweep": On the Power of the Wavefront Approach to Voronoi Diagrams. 19-32 BibTeX
Sunil Arya, Michiel H. M. Smid: Efficient Construction of a Bounded-Degree Spanner with Low Weight. 33-54 BibTeX
Torben Hagerup, Miroslaw Kutylowski: Fast Integer Merging on the EREW PRAM. 55-66 BibTeX
Jørgen Bang-Jensen, Mohamed El Haddad, Yannis Manoussakis, Teresa M. Przytycka: Parallel Algorithms for the Hamiltonian Cycle and Hamiltonian Path Problems in Semicomplete Bipartite Digraphs. 67-87 BibTeX

Ronald I. Greenberg, Jau-Der Shih: Minimizing Channel Density with Movable Terminals. 89-99 BibTeX
Frieda Granot, Jadranka Skorin-Kapov, Amir Tamir: Using Quadratic Programming to Solve High Multiplicity Scheduling Problems on Parallel Machines. 100-110 BibTeX
Francis Avnaim, Jean-Daniel Boissonnat, Olivier Devillers, Franco P. Preparata, Mariette Yvinec: Evaluating Signs of Determinants Using Single-Precision Arithmetic. 111-132 BibTeX
Jay N. Bhuyan, Jitender S. Deogun, Vijay V. Raghavan: Algorithms for the Boundary Selection Problem. 133-161 BibTeX
Laurent Alonso, Jean-Luc Remy, René Schott: A Linear-Time Algorithm for the Generation of Trees. 162-183 BibTeX
Kurt Mehlhorn, R. Sundar, Christian Uhrig: Maintaining Dynamic Sequences under Equality Tests in Polylogarithmic Time. 183-198 BibTeX
Robert F. Cohen, Peter Eades, Tao Lin, Frank Ruskey: Three-Dimensional Graph Drawing. 199-208 BibTeX

Noga Alon, Raphael Yuster, Uri Zwick: Finding and Counting Given Length Cycles. 209-223 BibTeX
Michael Kaufmann, Jop F. Sibeyn: Randomized Multipacket Routing and Sorting on Meshes. 224-244 BibTeX
Bernard Chazelle, Leonidas Palios: Decomposing the Boundary of a Nonconvex Polyhedron. 245-265 BibTeX
Lin Chen: Efficient Parallel Recognition of Some Circular Arc Graphs, II. 266-280 BibTeX
S. Guha, I. Suzuki: Proximity Problems for Points on a Rectilinear Plane with Rectangular Obstacles. 281-307 BibTeX
Rida A. Bazzi, Gil Neiger: The Complexity of Almost-Optimal Simultaneous Coordination. 308-321 BibTeX
Rephael Wenger: Randomized Quickhull. 322-329 BibTeX

Piotr Berman, Bhaskar DasGupta: Complexities of Efficient Solutions of Rectilinear Polygon Cover Problems. 331-356 BibTeX
Elon Rimon: Construction of C-Space Roadmaps from Local Sensory Data. What Should the Sensors Look For? 357-379 BibTeX
Marco Pellegrini: On Counting Pairs of Intersecting Segments and Off-Line Triangle Range Searching. 380-398 BibTeX
Yijie Han, Victor Y. Pan, John H. Reif: Efficient Parallel Algorithms for Computing All Pair Shortest Paths in Directed Graphs. 399-415 BibTeX
Sergio De Agostino, Rossella Petreschi, Andrea Sterbini: An O(n³) Recognition Algorithm for Bithreshold Graphs. 416-425 BibTeX
Susanne E. Hambrusch, Hung-Yi Tu: New Algorithms for Minimizing the Longest Wire Length During Circuit Compaction. 426-448 BibTeX
Noga Alon, Aravind Srinivasan: Improved Parallel Approximation of a Class of Integer Programming Problems. 449-462 BibTeX