Algorithmica, Volume 16, 1996

Volume 16, Number 1, July 1996

• Giuseppe Di Battista, Roberto Tamassia: Guest Editors' Introduction to the Special Issue on Graph Drwaing. 1-3
• Goos Kant: Drawing Planar Graphs Using the Canonical Ordering. 4-32
• Michael Jünger, Petra Mutzel: Maximum Planar Subgraphs and Nice Embeddings: Practical Layout Tools. 33-59
• Peter Eades, Sue Whitesides: The Realization Problem for Euclidean Minimum Spanning Trees in NP-Hard. 60-82
• Prosenjit Bose, William Lenhart, Giuseppe Liotta: Characterizing Proximity Trees. 83-110
• János Pach, Farhad Shahrokhi, Mario Szegedy: Applications of the Crossing Number. 111-117
• Farhad Shahrokhi, László A. Székely, Ondrej Sýkora, Imrich Vrto: Drawings of Graphs on Surfaces with Few Crossings. 118-131

Volume 16, Number 2, August 1996

• Xiaotie Deng, Christos H. Papadimitriou: Competitive Distributed Decision-Making. 133-150
• J. Ian Munro, Venkatesh Raman: Fast Stable In-Place Sorting with O (n) Data Moves. 151-160
• Shou-Hsuan Stephen Huang, Hongfei Liu, Rakesh M. Verma: A New Combinatorial Approach to Optimal Embeddings of Rectangles. 161-180
• Mark H. Nodine, Michael T. Goodrich, Jeffrey Scott Vitter: Blocking for External Graph Searching. 181-214
• David M. Choy, Ronald Fagin, Larry J. Stockmeyer: Efficiently Extendible Mappings for Balanced Data Distribution. 215-232
• Kurt Mehlhorn, Petra Mutzel: On the Embedding Phase of the Hopcroft and Tarjan Planarity Testing Algorithm. 233-242

Volume 16, Number 3, September 1996

• Sivaprakasam Sunder, Xin He: An NC Algorithm for Finding a Minimum Weighted Completion Time Schedule on Series Parallel Graphs. 243-262
• Dora Giammarresi, Giuseppe F. Italiano: Decremental 2- and 3-Connectivity on Planar Graphs. 263-287
• Costas S. Iliopoulos, D. W. G. Moore, Kunsoo Park: Covering a String. 288-297
• Andris Ambainis: Communication Complexity in a 3-Computer Model. 298-301
• Lusheng Wang, Tao Jiang, Eugene L. Lawler: Approximation Algorithms for Tree Alignment with a Given Phylogeny. 302-315
• Masato Edahiro: Equispreading Tree in Manhattan Distance. 316-338
• Jun-ya Takahashi, Hitoshi Suzuki, Takao Nishizeki: Shortest Noncrossing Paths in Plane Graphs. 339-357

Volume 16, Number 4/5, October/November 1996

• Michael Luby: Introduction to Special Issue on Randomized and Derandomized Algorithms. 359-366
• David Zuckerman: Simulating BPP Using a General Weak Random Source. 367-391
• Mark Jerrum, Umesh V. Vazirani: A Mildly Exponential Approximation Algorithm for the Permanent. 392-401
• Milena Mihail, Peter Winkler: On the Number of Eulerian Orientations of a Graph. 402-414
• Michael Luby, Boban Velickovic: On Deterministic Approximation of DNF. 415-433
• Noga Alon, Moni Naor: Derandomization, Witnesses for Boolean Matrix Multiplication and Construction of Perfect Hash Functions. 434-449
• Ketan Mulmuley: Randomized Geometric Algorithms and Pseudorandom Generators. 450-463
• Raimund Seidel, Cecilia R. Aragon: Randomized Search Trees. 464-497
• Jirí Matousek, Micha Sharir, Emo Welzl: A Subexponential Bound for Linear Programming. 498-516
• Richard M. Karp, Michael Luby, Friedhelm Meyer auf der Heide: Efficient PRAM Simulation on a Distributed Memory Machine. 517-542
• Helmut Alt, Leonidas J. Guibas, Kurt Mehlhorn, Richard M. Karp, Avi Wigderson: A Method for Obtaining Randomized Algorithms with Small Tail Probabilities. 543-547

Volume 16, Number 6, December 1996

• Michele Flammini, Giorgio Gambosi, Sandro Salomone: Interval Routing Schemes. 549-568
• Richard Cole, Michael T. Goodrich, Colm Ó'Dúnlaing: A Nearly Optimal Deterministic Parallel Voroni Diagram Algorithm. 569-617
• David Avis: Generating Rooted Triangulations Without Repetitions. 618-632
• Donald B. Johnson, Panagiotis Takis Metaxas: Optimal Algorithms for the Single and Multiple Vertex Updating Problems of a Minimum Spanning Tree. 633-648
• Mark Allen Weiss: Shellsort with a Constant Number of Increments. 649-654