| 1998 | 2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves. Roberto Solis-Oba |
| 1998 | A Fast Random Greedy Algorithm for the Component Commonality Problem. Ravi Kannan, Andreas Nolte |
| 1998 | A Functional Approach to External Graph Algorithms. James Abello, Adam L. Buchsbaum, Jeffery R. Westbrook |
| 1998 | A Probabilistic Zero-Test for Expressions Involving Root of Rational Numbers. Johannes Blömer |
| 1998 | A Randomized Algorithm for Two Servers on the Line (Extended Abstract). Yair Bartal, Marek Chrobak, Lawrence L. Larmore |
| 1998 | Adaptability and the Usefulness of Hints (Extended Abstract). Piotr Berman, Juan A. Garay |
| 1998 | Algorithms - ESA '98, 6th Annual European Symposium, Venice, Italy, August 24-26, 1998, Proceedings Gianfranco Bilardi, Giuseppe F. Italiano, Andrea Pietracaprina, Geppino Pucci |
| 1998 | An Experimental Study of Dynamic Algorithms for Directed Graphs. Daniele Frigioni, Tobias Miller, Umberto Nanni, Giulio Pasqualone, Guido Schäfer, Christos D. Zaroliagis |
| 1998 | Analogs and Duals of the MAST Problem for Sequences and Trees. Michael R. Fellows, Michael T. Hallett, Chantal Korostensky, Ulrike Stege |
| 1998 | Analyzing an Infinite Parallel Job Allocation Process. Micah Adler, Petra Berenbrink, Klaus Schröder |
| 1998 | Approximate Coloring of Uniform Hypergraphs (Extended Abstract). Michael Krivelevich, Benny Sudakov |
| 1998 | Augmenting Suffix Trees, with Applications. Yossi Matias, S. Muthukrishnan, Süleyman Cenk Sahinalp, Jacob Ziv |
| 1998 | Car-Pooling as a Data Structuring Device: The Soft Heap. Bernard Chazelle |
| 1998 | Complexity Estimates Depending on Condition and Round-Off Error. Felipe Cucker, Steve Smale |
| 1998 | Computer-Aided Way to Prove Theorems in Scheduling. Sergey V. Sevastianov, I. D. Tchernykh |
| 1998 | Computing the Edit-Distance between Unrooted Ordered Trees. Philip N. Klein |
| 1998 | Constructing Binary Space Partitions for Orthogonal Rectabgles in Practice. T. M. Murali, Pankaj K. Agarwal, Jeffrey Scott Vitter |
| 1998 | Delta-Stepping: A Parallel Single Source Shortest Path Algorithm. Ulrich Meyer, Peter Sanders |
| 1998 | Design and Analysis of Dynamic Processes: A Stochastic Approach. Eli Upfal |
| 1998 | Evaluating Server-Assisted Cache Replacement in the Web. Edith Cohen, Balachander Krishnamurthy, Jennifer Rexford |
| 1998 | External Memory Algorithms. Jeffrey Scott Vitter |
| 1998 | Fast Algorithms for for Linear Algebra Modulo N. Arne Storjohann, Thom Mulders |
| 1998 | Fault-Tolerant Broadcasting in Radio Networks (Extended Abstract). Evangelos Kranakis, Danny Krizanc, Andrzej Pelc |
| 1998 | Finding All the Best Swaps of a Minimum Diameter Spanning Tree under Transient Edge Failures. Enrico Nardelli, Guido Proietti, Peter Widmayer |
| 1998 | Finding an Optimal Path without Growing the Tree. Danny Z. Chen, Ovidiu Daescu, Xiaobo Hu, Jinhui Xu |
| 1998 | Fitting Points on the Real Line and Its Application to RH Mapping. Johan Håstad, Lars Ivansson, Jens Lagergren |
| 1998 | Fully Dynamic Shortest Paths and Negative Cycles Detection on Digraphs with Arbitrary Arc Weights. Daniele Frigioni, Alberto Marchetti-Spaccamela, Umberto Nanni |
| 1998 | Geometric Searching in Walkthrough Animations with Weak Spanners in Real Time. Matthias Fischer, Tamás Lukovszki, Martin Ziegler |
| 1998 | Improved Deterministic Parallel Padded Sorting. Ka Wong Chong, Edgar A. Ramos |
| 1998 | Intrinsic Near Quadratic Complexity Bounds for Real Multivariate Root Counting. J. Maurice Rojas |
| 1998 | Longest Common Subsequence from Fragments via Sparse Dynamic Programming. Brenda S. Baker, Raffaele Giancarlo |
| 1998 | Matching Medical Students to Pairs of Hospitals: A New Variation on a Well-Known Theme. Robert W. Irving |
| 1998 | Maximizing Job Completions Online. Bala Kalyanasundaram, Kirk Pruhs |
| 1998 | Minimal Triangulations for Graphs with "Few" Minimal Separators. Vincent Bouchitté, Ioan Todinca |
| 1998 | Moving-Target TSP and Related Problems. Christopher S. Helvig, Gabriel Robins, Alexander Zelikovsky |
| 1998 | Nearest Neighbor Load Balancing on Graphs. Ralf Diekmann, Andreas Frommer, Burkhard Monien |
| 1998 | New Bounds for Oblivious Mesh Routing. Kazuo Iwama, Yahiko Kambayashi, Eiji Miyano |
| 1998 | On Nonblocking Properties on the Benes Network. Petr Kolman |
| 1998 | Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property. Phillip G. Bradford, Mordecai J. Golin, Lawrence L. Larmore, Wojciech Rytter |
| 1998 | Positioning Guards at Fixed Height Above a Terrain - An Optimum Inapproximability Result. Stephan J. Eidenbenz, Christoph Stamm, Peter Widmayer |
| 1998 | Robust Region Approach to the Computation of Geometric Graphs (Extended Abstract). Fabrizio d'Amore, Paolo Giulio Franciosa, Giuseppe Liotta |
| 1998 | Techniques for Scheduling with Rejection. Daniel W. Engels, David R. Karger, Stavros G. Kolliopoulos, Sudipta Sengupta, R. N. Uma, Joel Wein |
| 1998 | Two-Center Problems for a Convex Polygon (Extended Abstract). Chan-Su Shin, Jung-Hyun Kim, Sung Kwon Kim, Kyung-Yong Chwa |