| 1989 | A Framework for Adaptive Routing in Multicomputer Networks. | John Y. Ngai, Charles L. Seitz |
| 1989 | Efficient Parallel Algorithms for Path Problems in Directed Graphs. | Joan M. Lucas, Marian Gunsher Sackrowitz |
| 1989 | Dynamic Tree Embeddings in Butterflies and Hypercubes. | Frank Thomson Leighton, Mark Newman, Abhiram G. Ranade, Eric J. Schwabe |
| 1989 | A 2 | Frank Thomson Leighton, Fillia Makedon, Ioannis G. Tollis |
| 1989 | Conflict-Free Access of Arrays in a Parallel Processor. | De-Lei Lee, Y. H. Wang |
| 1989 | The Power of Parallel Pointer Manipulation. | Tak Wah Lam, Walter L. Ruzzo |
| 1989 | Multi-Packet-Routing on Mesh Connected Arrays. | Manfred Kunde, Thomas Tensi |
| 1989 | Cost-Bandwidth Tradeoffs for Communication Networks. | Clyde P. Kruskal, Marc Snir |
| 1989 | Technologies for Low Latency Interconnection Switches. | Thomas F. Knight Jr. |
| 1989 | Optimal Parallel Suffix-Prefix Matching Algorithm and Applications. | Zvi M. Kedem, Gad M. Landau, Krishna V. Palem |
| 1989 | On Parallel Evaluation of Game Trees. | Richard M. Karp, Yanjun Zhang |
| 1989 | Lower Bounds and Efficient Algorithms for Multiprocessor Scheduling of Dags with Communication Delays. | Hermann Jung, Lefteris M. Kirousis, Paul G. Spirakis |
| 1989 | Deterministic P-RAM Simulation with Constant Redundancy. | Scot W. Hornick, Franco P. Preparata |
| 1989 | Matching Partition a Linked List and Its Optimization. | Yijie Han |
| 1989 | Intersecting Line Segments in Parallel With an Output-Sensitive Number of Processors. | Michael T. Goodrich |
| 1989 | A More practical PRAM Model. | Phillip B. Gibbons |
| 1989 | Advances in Homotopic Layout Compaction. | Shaodi Gao, Michael Kaufmann, F. Miller Maley |
| 1989 | The Virtual Time Machine. | Richard Fujimoto |
| 1989 | Towards Understanding Exclusive Read. | Faith E. Fich, Avi Wigderson |
| 1989 | On the Number of Rounds Necessary to Disseminate Information. | Shimon Even, Burkhard Monien |
| 1989 | An Optimal Parallel Dictionary. | Martin Dietzfelbinger, Friedhelm Meyer auf der Heide |
| 1989 | On the Parallel Complexity of Integer Programming. | Xiaotie Deng |
| 1989 | A Lower Bound on the Size of Shellsort Networks. | Robert Cypher |
| 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 |