| 1989 | Digital Data Structures and Order Statistics. | Wojciech Szpankowski |
| 1989 | Self-Adjusting k-ary Search Trees. | Murray Sherk |
| 1989 | Structured NC. | Bertha Scholten, Jan van Leeuwen |
| 1989 | Selecting the kth Largest-Area Convex Polygon. | Jeffrey S. Salowe |
| 1989 | Computing the Furthest Site Voronoi Diagram for a Set of Discs (Preliminary Report). | David Rappaport |
| 1989 | Linear Algorithms for Parity Path and Two Path Problems on Circular-Arc Graph. | A. Srinivasa Rao, C. Pandu Rangan |
| 1989 | Skip Lists: A Probabilistic Alternative to Balanced Trees. | William W. Pugh |
| 1989 | Efficient Spatial Point Location (Extended Abstract). | Franco P. Preparata, Roberto Tamassia |
| 1989 | A Fast Algorithm for Melding Splay Trees. | Graeme S. Port, Alistair Moffat |
| 1989 | Complexity Issues in Tree-Based Version Control. | Naomi Nishimura |
| 1989 | Sorting with Minimum Data Movement (Preliminary Draft). | J. Ian Munro, Venkatesh Raman |
| 1989 | Optimal Hypercube Algorithms for Labeled Images (Preliminary Version). | Russ Miller, Quentin F. Stout |
| 1989 | Discs and Other Related Data Structures. | Fabrizio Luccio, Mireille Rgnier, Ren Schott |
| 1989 | Heapsort - Adapted for Presorted Files. | Christos Levcopoulos, Ola Petersson |
| 1989 | Weighted Visibility Graphs of Bars and Related Flow Problems (Extended Abstract). | David G. Kirkpatrick, Stephen K. Wismath |
| 1989 | A Polynomial Time Algorithm for the Local Testability Problem of Deterministic Finite Automata. | Sam M. Kim, Robert McNaughton, Robert McCloskey |
| 1989 | Parallel Algorithms for the Subgraph Homeomorphism Problem. | Samir Khuller |
| 1989 | Computing the Kernel of a Point Set in a Polygon (Extended Abstract). | Yan Ke, Joseph O'Rourke |
| 1989 | The Delauney Triangulation Closely Approximates the Complete Euclidean Graph. | J. Mark Keil, Carl A. Gutwin |
| 1989 | Dynamic Data Structures for Series Parallel Digraphs (Preliminary Version). | Giuseppe F. Italiano, Alberto Marchetti-Spaccamela, Umberto Nanni |
| 1989 | An Efficient All-Parses Systolic Algorithm for General Context-Free Parsing. | Oscar H. Ibarra, Michael A. Palis |
| 1989 | Finding All Shortest Path Edge Sequences on a Convex Polyhedron. | Yie-Huei Hwang, Ruei-Chuan Chang, Hung-Yi Tu |
| 1989 | Weighted Orthogonal Linear L | Michael E. Houle, Hiroshi Imai, Keiko Imai, Jean-Marc Robert |
| 1989 | Stabbing Parallel Segments with a Convex Polygon (Extended Abstract). | Michael T. Goodrich, Jack Snoeyink |
| 1989 | Constructing the Voronoi Diagram of a Set of Line Segments in Parallel (Preliminary Version). | Michael T. Goodrich, Colm 'Dnlaing, Chee-Keng Yap |