Algorithmica, Volume 16, 1996

Volume 16, Number 1, July 1996

Special Issue on Graph Drawing

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

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

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

Special Issue Randomized and Derandomized Algorithms

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

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

Last update Tue May 21 18:19:43 2013 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page