| 1998 | A New Approximation Algorithm for the Planar Augmentation Problem. | Sergej Fialko, Petra Mutzel |
| 1998 | On Local Register Allocation. | Martin Farach, Vincenzo Liberatore |
| 1998 | A Probabilistic Algorithm for Updating Files over a Communication Link. | Alexandre V. Evfimievski |
| 1998 | Fast Hierarchical Clustering and Other Applications of Dynamic Closest Pairs. | David Eppstein |
| 1998 | Go with the Winners for Graph Bisection. | Tassos Dimitriou, Russell Impagliazzo |
| 1998 | The Ultimate Interval Graph Recognition Algorithm? (Extended Abstract). | Derek G. Corneil, Stephan Olariu, Lorna Stewart |
| 1998 | Approximate String Matching: A Simpler Faster Algorithm. | Richard Cole, Ramesh Hariharan |
| 1998 | The Analysis of Hybrid Trie Structures. | Julien Clment, Philippe Flajolet, Brigitte Valle |
| 1998 | Competive Algorithms for Multilevel Caching and Relaxed List Update (Extended Abstract). | Marek Chrobak, John Noga |
| 1998 | LRU is Better than FIFO. | Marek Chrobak, John Noga |
| 1998 | A 3/2-Approximation Algorithm for Sorting by Reversals. | David A. Christie |
| 1998 | The Dynamic Servers Problem. | Moses Charikar, Dan Halperin, Rajeev Motwani |
| 1998 | Approximation Algorithms for Directed Steiner Problems. | Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, Ming Li |
| 1998 | Output-Sensitive Generation of Random Events. | Paul B. Callahan |
| 1998 | Mutual Search (Extended Abstract). | Harry Buhrman, Matthew K. Franklin, Juan A. Garay, Jaap-Henk Hoepman, John Tromp, Paul M. B. Vitnyi |
| 1998 | Beating the 2 Delta Bound for Approximately Counting Colourings: A Computer-Assisted Proof of Rapid Mixing. | Russ Bubley, Martin E. Dyer, Catherine S. Greenhill |
| 1998 | Faster Random Generation of Linear Extensions. | Russ Bubley, Martin E. Dyer |
| 1998 | Finger Search Trees with Constant Insertion Time. | Gerth Stlting Brodal |
| 1998 | Linear-Time Register Allocation for a Fixed Number of Registers. | Hans L. Bodlaender, Jens Gustedt, Jan Arne Telle |
| 1998 | Learning Deterministic Finite Automata from Smallest Counterexamples. | Andreas Birkendorf, Andreas Bker, Hans Ulrich Simon |
| 1998 | An Efficient Algorithm for the Three-Dimensional Diameter Problem. | Sergei Bespamyatnikh |
| 1998 | Sparse 0-1-Matrices and Forbidden Hypergraphs (Extended Abstract). | Claudia Bertram-Kretzberg, Thomas Hofmeister, Hanno Lefmann |
| 1998 | Flow and Stretch Metrics for Scheduling Continuous Job Streams. | Michael A. Bender, Soumen Chakrabarti, S. Muthukrishnan |
| 1998 | Augmenting Undirected Edge Connectivity in (n | Andrs A. Benczr, David R. Karger |
| 1998 | Minimizing Service and Operation Costs of Periodic Scheduling (Extended Abstract). | Amotz Bar-Noy, Randeep Bhatia, Joseph Naor, Baruch Schieber |