| 1989 | A 2 Frank Thomson Leighton, Fillia Makedon, Ioannis G. Tollis |
| 1989 | A Framework for Adaptive Routing in Multicomputer Networks. John Y. Ngai, Charles L. Seitz |
| 1989 | A Lazy Cache Algorithm. Yehuda Afek, Geoffrey M. Brown, Michael Merritt |
| 1989 | A Lower Bound on the Size of Shellsort Networks. Robert Cypher |
| 1989 | A More practical PRAM Model. Phillip B. Gibbons |
| 1989 | Advances in Homotopic Layout Compaction. Shaodi Gao, Michael Kaufmann, F. Miller Maley |
| 1989 | An Efficient Parallel Algorithm for Computing a Large Independent Set in a Plan Graph. Marek Chrobak, Joseph Naor |
| 1989 | An Optimal Parallel Dictionary. Martin Dietzfelbinger, Friedhelm Meyer auf der Heide |
| 1989 | Conflict-Free Access of Arrays in a Parallel Processor. De-Lei Lee, Y. H. Wang |
| 1989 | Constructing Trees in Parallel. Mikhail J. Atallah, S. Rao Kosaraju, Lawrence L. Larmore, Gary L. Miller, Shang-Hua Teng |
| 1989 | Cost-Bandwidth Tradeoffs for Communication Networks. Clyde P. Kruskal, Marc Snir |
| 1989 | Deterministic P-RAM Simulation with Constant Redundancy. Scot W. Hornick, Franco P. Preparata |
| 1989 | Dynamic Tree Embeddings in Butterflies and Hypercubes. Frank Thomson Leighton, Mark Newman, Abhiram G. Ranade, Eric J. Schwabe |
| 1989 | Efficient Parallel Algorithms for Path Problems in Directed Graphs. Joan M. Lucas, Marian Gunsher Sackrowitz |
| 1989 | Embedding of M. Y. Chan |
| 1989 | Fast Parallel Algorithms for the Unit Cost Editing Distance Between Trees. Dennis E. Shasha, Kaizhong Zhang |
| 1989 | Fault Tolerance in Hypercube-Derivative Networks. Fred S. Annexstein |
| 1989 | Four Vector-Matrix Primitives. Ajit Agrawal, Guy E. Blelloch, Robert L. Krawitz, C. A. Phillips |
| 1989 | Intersecting Line Segments in Parallel With an Output-Sensitive Number of Processors. Michael T. Goodrich |
| 1989 | Load Balancing, Selection Sorting on the Hypercube. C. Greg Plaxton |
| 1989 | Locating Faults in a Constant Number of Parallel Testing Rounds. Richard Beigel, S. Rao Kosaraju, Gregory F. Sullivan |
| 1989 | Lower Bounds and Efficient Algorithms for Multiprocessor Scheduling of Dags with Communication Delays. Hermann Jung, Lefteris M. Kirousis, Paul G. Spirakis |
| 1989 | Matching Partition a Linked List and Its Optimization. Yijie Han |
| 1989 | Multi-Packet-Routing on Mesh Connected Arrays. Manfred Kunde, Thomas Tensi |
| 1989 | On Communication Latency in PRAM Computations. Alok Aggarwal, Ashok K. Chandra, Marc Snir |
| 1989 | On Parallel Evaluation of Game Trees. Richard M. Karp, Yanjun Zhang |
| 1989 | On the Number of Rounds Necessary to Disseminate Information. Shimon Even, Burkhard Monien |
| 1989 | On the Parallel Complexity of Integer Programming. Xiaotie Deng |
| 1989 | Optimal On-Line Load Balancing. Gregory E. Shannon |
| 1989 | Optimal Parallel Algorithms for Transitive Closure and Point Location in Planar Structures. Roberto Tamassia, Jeffrey Scott Vitter |
| 1989 | Optimal Parallel Suffix-Prefix Matching Algorithm and Applications. Zvi M. Kedem, Gad M. Landau, Krishna V. Palem |
| 1989 | Optimal VLSI Architectures for Multidimensional DFT. Gianfranco Bilardi, Scot W. Hornick, Majid Sarrafzadeh |
| 1989 | Parallel Graph Contraction. C. A. Philips |
| 1989 | Parallel RAMs with Bounded Memory Wordsize. Stephen J. Bellantoni |
| 1989 | Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, SPAA '89, Santa Fe, New Mexico, USA, June 18-21, 1989 Frank Thomson Leighton |
| 1989 | Processor Networks and Interconnection Networks Without Long Wires. C. P. Beigel, Clyde P. Kruskal |
| 1989 | Robust Algorithms for Packet Routing in a Mesh. Prabhakar Raghavan |
| 1989 | Run-Time Parallelization and Scheduling of Loops. Doug Baxter, Ravi Mirchandaney, Joel H. Saltz |
| 1989 | Square Meshes Are Not Always Optimal. Amotz Bar-Noy, Danny Peleg |
| 1989 | Systolic Implementations of a Move-to-Front Text Compressor. Clark D. Thomborson, Belle W. Y. Wei |
| 1989 | Technologies for Low Latency Interconnection Switches. Thomas F. Knight Jr. |
| 1989 | The APRAM: Incorporating Asynchrony into the PRAM Model. Richard Cole, Ofer Zajicek |
| 1989 | The Communication Complexity of Several Problems in Matrix Computation. Jeff I. Chu, Georg Schnitger |
| 1989 | The Power of Parallel Pointer Manipulation. Tak Wah Lam, Walter L. Ruzzo |
| 1989 | The Virtual Time Machine. Richard Fujimoto |
| 1989 | Towards Understanding Exclusive Read. Faith E. Fich, Avi Wigderson |