| 1998 | Generalized Graph Colorability and Compressibility of Boolean Formulae. | Richard Nock, Pascal Jappy, Jean Sallantin |
| 1998 | Randomized O (log log n)-Round Leader Election Protocols in Packet Radio Networks. | Koji Nakano, Stephan Olariu |
| 1998 | Polyhedral Structure of Submodular and Posi-modular Systems. | Hiroshi Nagamochi, Toshihide Ibaraki |
| 1998 | An Efficient NC Algorithm for a Sparse k-Edge-Connectivity Certificate. | Hiroshi Nagamochi, Toru Hasunuma |
| 1998 | Two-Layer Planarization in Graph Drawing. | Petra Mutzel, Ren Weiskircher |
| 1998 | A Quantum Polynomial Time Algorithm in Worst Case for Simon's Problem. | Takashi Mihara, Shao Chin Sung |
| 1998 | The Steiner Tree Problem in Lambda | Guo-Hui Lin, Guoliang Xue |
| 1998 | Fast Algorithms for Independent Domination and Efficient Domination in Trapezoid Graphs. | Yaw-Ling Lin |
| 1998 | On the Complexity of Free Monoid Morphisms. | Klaus-Jrn Lange, Pierre McKenzie |
| 1998 | Selecting the k Largest Elements with Parity Tests. | Tak Wah Lam, Hing-Fung Ting |
| 1998 | Space-Efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs. | Philip N. Klein, Hsueh-I Lu |
| 1998 | K-Edge and 3-Vertex Connectivity Augmentation in an Arbitrary Multigraph. | Toshimasa Ishii, Hiroshi Nagamochi, Toshihide Ibaraki |
| 1998 | Characterization of Efficiently Solvable Problems on Distance-Hereditary Graphs. | Sun-Yuan Hsieh, Chin-Wen Ho, Tsan-sheng Hsu, Ming-Tat Ko, Gen-Huey Chen |
| 1998 | Finding Planar Geometric Automorphisms in Planar Graphs. | Seok-Hee Hong, Peter Eades, Sang Ho Lee |
| 1998 | A Capacitated Vehicle Routing Problem on a Tree. | Shin-ya Hamaguchi, Naoki Katoh |
| 1998 | Random Regular Graphs with Edge Faults: Expansion through Cores. | Andreas Goerdt |
| 1998 | On the Multiple Gene Duplication Problem. | Michael R. Fellows, Michael T. Hallett, Ulrike Stege |
| 1998 | Maximizing the Number of Connections in Optical Tree Networks. | Thomas Erlebach, Klaus Jansen |
| 1998 | Disjunctions of Horn Theories and Their Cores. | Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino |
| 1998 | Inapproximability Results for Guarding Polygons without Holes. | Stephan J. Eidenbenz |
| 1998 | Randomized K-Dimensional Binary Search Trees. | Amalia Duch, Vladimir Estivill-Castro, Conrado Martnez |
| 1998 | Computing Orthogonal Drawings in a Variable Embedding Setting. | Walter Didimo, Giuseppe Liotta |
| 1998 | A Parallel Algorithm for Sampling Matchings from an Almost Uniform Distribution. | Josep Daz, Jordi Petit, Panagiotis Psycharis, Maria J. Serna |
| 1998 | Checking Programs Discreetly: Demonstrating Result-Correctness Efficiently while Concealing it. | Giovanni Di Crescenzo, Kouichi Sakurai, Moti Yung |
| 1998 | Computing Weighted Rectilinear Median and Center Set in the Presence of Obstacles. | Joonsoo Choi, Chan-Su Shin, Sung Kwon Kim |