| 1989 | A Fast Algorithm for Melding Splay Trees. Graeme S. Port, Alistair Moffat |
| 1989 | A New Search Time Update Time Tradeoff for the Implicit Dictionary. Philippe Derome |
| 1989 | A Polynomial Time Algorithm for the Local Testability Problem of Deterministic Finite Automata. Sam M. Kim, Robert McNaughton, Robert McCloskey |
| 1989 | Algorithms and Data Structures, Workshop WADS '89, Ottawa, Canada, August 17-19, 1989, Proceedings Frank K. H. A. Dehne, Jörg-Rüdiger Sack, Nicola Santoro |
| 1989 | An Efficient Algorithm for Finding all Maximal Square Blocks in a Matrix. Heinz Breu |
| 1989 | An Efficient All-Parses Systolic Algorithm for General Context-Free Parsing. Oscar H. Ibarra, Michael A. Palis |
| 1989 | Analysis of KDT-Trees: KD-Trees Improved by Local Reogranisations. Walter Cunto, Gustavo Lau, Philippe Flajolet |
| 1989 | Augmentation Problems on Hierarchically Defined Graphs (Preliminary Version). David Fernández-Baca, Mark A. Williams |
| 1989 | Combinatorial and Computational Results for Line Arrangements in Space. Herbert Edelsbrunner |
| 1989 | Complexity Issues in Tree-Based Version Control. Naomi Nishimura |
| 1989 | Computing the Center of Area of a Polygon. Matthew Díaz, Joseph O'Rourke |
| 1989 | Computing the Furthest Site Voronoi Diagram for a Set of Discs (Preliminary Report). David Rappaport |
| 1989 | Computing the Kernel of a Point Set in a Polygon (Extended Abstract). Yan Ke, Joseph O'Rourke |
| 1989 | Computing the Minimum Visible Vertex Distance between Two Polygons (Preliminary Version). Alok Aggarwal, Shlomo Moran, Peter W. Shor, Subhash Suri |
| 1989 | Constructing the Voronoi Diagram of a Set of Line Segments in Parallel (Preliminary Version). Michael T. Goodrich, Colm Ó'Dúnlaing, Chee-Keng Yap |
| 1989 | Digital Data Structures and Order Statistics. Wojciech Szpankowski |
| 1989 | Discs and Other Related Data Structures. Fabrizio Luccio, Mireille Régnier, René Schott |
| 1989 | Dynamic Data Structures for Series Parallel Digraphs (Preliminary Version). Giuseppe F. Italiano, Alberto Marchetti-Spaccamela, Umberto Nanni |
| 1989 | Efficient Spatial Point Location (Extended Abstract). Franco P. Preparata, Roberto Tamassia |
| 1989 | Efficient Text Searching of Regular Expressions. Ricardo A. Baeza-Yates, Gaston H. Gonnet |
| 1989 | Finding All Shortest Path Edge Sequences on a Convex Polyhedron. Yie-Huei Hwang, Ruei-Chuan Chang, Hung-Yi Tu |
| 1989 | Fully Persistent Arrays (Extended Array). Paul F. Dietz |
| 1989 | Galleries, Light Matchings and Visibility Graphs. Jurek Czyzowicz, Ivan Rival, Jorge Urrutia |
| 1989 | Heapsort - Adapted for Presorted Files. Christos Levcopoulos, Ola Petersson |
| 1989 | Improving Partial Rebuilding by Using Simple Balance Criteria. Arne Andersson |
| 1989 | Linear Algorithms for Parity Path and Two Path Problems on Circular-Arc Graph. A. Srinivasa Rao, C. Pandu Rangan |
| 1989 | Linear Time Algorithms for Computing Reachability Regions from Polygonal Figures. Rongyao Zhao |
| 1989 | Motion Planning in the CL-Environment (Extended Abstract). Chee-Keng Yap, Helmut Alt |
| 1989 | NC Algorithms for Circular-Arc Graphs. Lin Chen |
| 1989 | On Linear Time Minor Tests and Depth First Search. Hans L. Bodlaender |
| 1989 | On the Complexity of Single Row Routing Problems. Adair Dingle, Ivan Hal Sudborough |
| 1989 | On the Performance of Orthogonal Range Queries in Multiattribute and Doubly Chained Trees. Danièle Gardy, Philippe Flajolet, Claude Puech |
| 1989 | Optimal Algorithms for List Indexing and Subset Rank. Paul F. Dietz |
| 1989 | Optimal Channel Placement for Multi-Terminal Nets. Mikhail J. Atallah, Susanne E. Hambrusch |
| 1989 | Optimal Hypercube Algorithms for Labeled Images (Preliminary Version). Russ Miller, Quentin F. Stout |
| 1989 | Parallel Algorithms for Cographs Recognition and Applications. Gur Saran Adhar, Shietung Peng |
| 1989 | Parallel Algorithms for the Subgraph Homeomorphism Problem. Samir Khuller |
| 1989 | Probabilistic Analysis of Algorithms and Data Structures. Luc Devroye |
| 1989 | Selecting the kth Largest-Area Convex Polygon. Jeffrey S. Salowe |
| 1989 | Self-Adjusting k-ary Search Trees. Murray Sherk |
| 1989 | Skip Lists: A Probabilistic Alternative to Balanced Trees. William W. Pugh |
| 1989 | Sorting with Minimum Data Movement (Preliminary Draft). J. Ian Munro, Venkatesh Raman |
| 1989 | Stabbing Parallel Segments with a Convex Polygon (Extended Abstract). Michael T. Goodrich, Jack Snoeyink |
| 1989 | String Searching Algorithms Revisited. Ricardo A. Baeza-Yates |
| 1989 | Structured NC. Bertha Scholten, Jan van Leeuwen |
| 1989 | The Delauney Triangulation Closely Approximates the Complete Euclidean Graph. J. Mark Keil, Carl A. Gutwin |
| 1989 | The Distribution of Keys in a Binary Heap. Mark Allen Weiss, Jainendra K. Navlakha |
| 1989 | Using Bounded Degree Spanning Trees in the Design of Efficient Algorithms on Claw-Free Graphs. Marek Chrobak, Joseph Naor, Mark B. Novick |
| 1989 | Weighted Orthogonal Linear L Michael E. Houle, Hiroshi Imai, Keiko Imai, Jean-Marc Robert |
| 1989 | Weighted Visibility Graphs of Bars and Related Flow Problems (Extended Abstract). David G. Kirkpatrick, Stephen K. Wismath |