Front matter
1-2
Efficient text searching of regular expressions
Ricardo A. Baeza-Yates and Gaston H. Gonnet
3-11
Efficient spatial point location
Extended abstract
Franco P. Preparata and Roberto Tamassia
12-23
Constructing the Voronoi diagram of a set of line segments in parallel
Preliminary version
Michael T. Goodrich, Colm Ó'Dúnlaing and Chee K. Yap
24-38
Analysis of kdt-trees: Kd-trees improved by local reorganisations
Walter Cunto, Gustavo Lau and Philippe Flajolet
39-46
Optimal algorithms for List Indexing and Subset Rank
Paul F. Dietz
47-56
The Delaunay triangulation closely approximates the complete Euclidean graph
J. Mark Keil and Carl A. Gutwin
57-66
Computing the furthest site voronoi diagram for a set of discs
Preliminary report
David Rappaport
67-74
Fully persistent arrays
Extended abstract
Paul F. Dietz
75-96
String searching algorithms revisited
Ricardo A. Baeza-Yates
97-114
Optimal channel placement for multi-terminal nets
Mikhail J. Atallah and Susanne E. Hambrusch
115-134
Computing the minimum visible vertex distance between two polygons
Preliminar version
Alok Aggarwal, Shlomo Moran, Peter W. Shor and Subhash Suri
135-146
Computing the kernel of a point set in a polygon
Extended abstract
Yan Ke and Joseph O'Rourke
147-162
Using bounded degree spanning trees in the design of efficient algorithms on claw-free graphs
Marek Chrobak, Joseph Naor and Mark B. Novick
163-170
Linear time algorithms for computing reachability regions from polygonal figures
Rongyao Zhao
171-182
Computing the center of area of a polygon
Matthew Díaz and Joseph O'Rourke
183-191
Weighted orthogonal linear L∞-approximation and applications
Michael E. Houle, Hiroshi Imai, Keiko Imai and Jean-Marc Robert
192-205
Discs and other related data structures
Fabrizio Luccio, Mireille Régnier and René Schott
206-217
Digital data structures and order statistics
Wojciech Szpankowski
218-229
On the performance of orthogonal range queries in multiattribute and doubly chained trees
Danièle Gardy, Philippe Flajolet and Claude Puech
230
Probabilistic analysis of algorithms and data structures
Luc Devroye
231-242
Stabbing parallel segments with a convex polygon
Extended abstract
Michael T. Goodrich and Jack Scott Snoeyink
243-250
Selecting the Kth largest-area convex polygon
Jeffrey S. Salowe
251-266
Finding All Shortest Path Edge Sequences on a convex polyhedron
Yie-Huei Hwang, Ruei-Chuan Chang and Hung-Yi Tu
267-290
Linear algorithms for parity path and two path problems on circular-arc graph
A. Srinivasa Rao and C. Pandu Rangan
291-302
NC algorithms for circular-arc graphs
Lin Chen
303-315
Parallel algorithms for the subgraph homeomorphism problem
Samir Khuller
316-324
Galleries, light matchings and visibility graphs
Jurek Czyzowicz, Ivan Rival and Jorge Urrutia
325-334
Weighted visibility graphs of bars and related flow problems
Extended abstract
David G. Kirkpatrick and Stephen K. Wismath
335-351
Parallel algorithms for cographs recognition and applications
Gur Saran Adhar and Shietung Peng
352-372
Dynamic data structures for series parallel digraphs
preliminary version
Giuseppe F. Italiano, Alberto Marchetti Spaccamela and Umberto Nanni
373-380
Motion planning in the CL-environment
Extended abstract
Chee-Keng Yap and Helmut Alt
381-392
Self-adjusting k-ary search trees
Murray Sherk
393-402
Improving partial rebuilding by using simple balance criteria
Arne Andersson
403-419
An efficient all-parses systolic algorithm for general context-free parsing
Oscar H. Ibarra and Michael A. Palis
420-436
A polynomial time algorithm for the local testability problem of deterministic finite automata
Sam Kim, Robert McNaughton and Robert McCloskey
437-449
Skip lists: A probabilistic alternative to balanced trees
William Pugh
450-459
A fast algorithm for melding splay trees
Graeme Port and Alistair Moffat
460-471
An efficient algorithm for finding all maximal square blocks in a matrix
Heinz Breu
472-486
Complexity issues in tree-based version control
Naomi Nishimura
487-498
Structured NC
Bertha Scholten and Jan van Leeuwen
499-509
Heapsort—Adapted for presorted files
Christos Levcopoulos and Ola Petersson
510-516
The distribution of keys in a binary heap
Mark Allen Weiss and Jainendra K. Navlakha
517-528
Optimal hypercube algorithms for labeled images
Preliminary version
Russ Miller and Quentin F. Stout
529-540
On the complexity of single row routing problems
Adair Dingle and I. Hal Sudborough
541-551
A new search time update time tradeoff for the implicit dictionary
Philippe Derome
552-562
Sorting with minimum data movement (preliminary draft)
J. Ian Munro and Venkatesh Raman
563-576
Augmentation problems on hierarchically defined graphs
Preliminary version
David Fernández-Baca and Mark A. Williams
577-590
On linear time minor tests and depth first search
Hans L. Bodlaender
591
Combinatorial and computational results for line arrangements in space
Herbert Edelsbrunner
Back matter