| 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 | Augmenting Suffix Trees, with Applications. | Yossi Matias, S. Muthukrishnan, Sleyman Cenk Sahinalp, Jacob Ziv |
| 1998 | Approximate Coloring of Uniform Hypergraphs (Extended Abstract). | Michael Krivelevich, Benny Sudakov |
| 1998 | Fault-Tolerant Broadcasting in Radio Networks (Extended Abstract). | Evangelos Kranakis, Danny Krizanc, Andrzej Pelc |
| 1998 | On Nonblocking Properties on the Benes Network. | Petr Kolman |
| 1998 | Computing the Edit-Distance between Unrooted Ordered Trees. | Philip N. Klein |
| 1998 | A Fast Random Greedy Algorithm for the Component Commonality Problem. | Ravi Kannan, Andreas Nolte |
| 1998 | Maximizing Job Completions Online. | Bala Kalyanasundaram, Kirk Pruhs |
| 1998 | New Bounds for Oblivious Mesh Routing. | Kazuo Iwama, Yahiko Kambayashi, Eiji Miyano |
| 1998 | Matching Medical Students to Pairs of Hospitals: A New Variation on a Well-Known Theme. | Robert W. Irving |
| 1998 | Moving-Target TSP and Related Problems. | Christopher S. Helvig, Gabriel Robins, Alexander Zelikovsky |
| 1998 | Fitting Points on the Real Line and Its Application to RH Mapping. | Johan Hstad, Lars Ivansson, Jens Lagergren |
| 1998 | An Experimental Study of Dynamic Algorithms for Directed Graphs. | Daniele Frigioni, Tobias Miller, Umberto Nanni, Giulio Pasqualone, Guido Schfer, Christos D. Zaroliagis |
| 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, Tams Lukovszki, Martin Ziegler |
| 1998 | Analogs and Duals of the MAST Problem for Sequences and Trees. | Michael R. Fellows, Michael T. Hallett, Chantal Korostensky, Ulrike Stege |
| 1998 | Techniques for Scheduling with Rejection. | Daniel W. Engels, David R. Karger, Stavros G. Kolliopoulos, Sudipta Sengupta, R. N. Uma, Joel Wein |
| 1998 | Positioning Guards at Fixed Height Above a Terrain - An Optimum Inapproximability Result. | Stephan J. Eidenbenz, Christoph Stamm, Peter Widmayer |
| 1998 | Nearest Neighbor Load Balancing on Graphs. | Ralf Diekmann, Andreas Frommer, Burkhard Monien |
| 1998 | Robust Region Approach to the Computation of Geometric Graphs (Extended Abstract). | Fabrizio d'Amore, Paolo Giulio Franciosa, Giuseppe Liotta |
| 1998 | Complexity Estimates Depending on Condition and Round-Off Error. | Felipe Cucker, Steve Smale |
| 1998 | Evaluating Server-Assisted Cache Replacement in the Web. | Edith Cohen, Balachander Krishnamurthy, Jennifer Rexford |
| 1998 | Improved Deterministic Parallel Padded Sorting. | Ka Wong Chong, Edgar A. Ramos |
| 1998 | Finding an Optimal Path without Growing the Tree. | Danny Z. Chen, Ovidiu Daescu, Xiaobo Hu, Jinhui Xu |