| 1989 | On the Performance of Orthogonal Range Queries in Multiattribute and Doubly Chained Trees. | Danile Gardy, Philippe Flajolet, Claude Puech |
| 1989 | Augmentation Problems on Hierarchically Defined Graphs (Preliminary Version). | David Fernndez-Baca, Mark A. Williams |
| 1989 | Combinatorial and Computational Results for Line Arrangements in Space. | Herbert Edelsbrunner |
| 1989 | On the Complexity of Single Row Routing Problems. | Adair Dingle, Ivan Hal Sudborough |
| 1989 | Fully Persistent Arrays (Extended Array). | Paul F. Dietz |
| 1989 | Optimal Algorithms for List Indexing and Subset Rank. | Paul F. Dietz |
| 1989 | Computing the Center of Area of a Polygon. | Matthew Daz, Joseph O'Rourke |
| 1989 | Probabilistic Analysis of Algorithms and Data Structures. | Luc Devroye |
| 1989 | A New Search Time Update Time Tradeoff for the Implicit Dictionary. | Philippe Derome |
| 1989 | Galleries, Light Matchings and Visibility Graphs. | Jurek Czyzowicz, Ivan Rival, Jorge Urrutia |
| 1989 | Analysis of KDT-Trees: KD-Trees Improved by Local Reogranisations. | Walter Cunto, Gustavo Lau, Philippe Flajolet |
| 1989 | Using Bounded Degree Spanning Trees in the Design of Efficient Algorithms on Claw-Free Graphs. | Marek Chrobak, Joseph Naor, Mark B. Novick |
| 1989 | NC Algorithms for Circular-Arc Graphs. | Lin Chen |
| 1989 | An Efficient Algorithm for Finding all Maximal Square Blocks in a Matrix. | Heinz Breu |
| 1989 | On Linear Time Minor Tests and Depth First Search. | Hans L. Bodlaender |
| 1989 | Efficient Text Searching of Regular Expressions. | Ricardo A. Baeza-Yates, Gaston H. Gonnet |
| 1989 | String Searching Algorithms Revisited. | Ricardo A. Baeza-Yates |
| 1989 | Optimal Channel Placement for Multi-Terminal Nets. | Mikhail J. Atallah, Susanne E. Hambrusch |
| 1989 | Improving Partial Rebuilding by Using Simple Balance Criteria. | Arne Andersson |
| 1989 | Computing the Minimum Visible Vertex Distance between Two Polygons (Preliminary Version). | Alok Aggarwal, Shlomo Moran, Peter W. Shor, Subhash Suri |
| 1989 | Parallel Algorithms for Cographs Recognition and Applications. | Gur Saran Adhar, Shietung Peng |