| 1996 | The Structure of Circular Decomposable Metrics. | George Christopher, Martin Farach, Michael A. Trick |
| 1996 | Negative-Cycle Detection Algorithms. | Boris V. Cherkassky, Andrew V. Goldberg |
| 1996 | Parallel Algorithms for Partitioning Sorted Sets and Related Problems. | Danny Z. Chen, Wei Chen, Koichi Wada, Kimio Kawaguchi |
| 1996 | Parallel Algorithms for Series Parallel Graphs. | Hans L. Bodlaender, Babette de Fluiter |
| 1996 | A Lower Bound for Nearly Minimal Adaptive and Hot Potato Algorithms. | Ishai Ben-Aroya, Donald D. Chinn, Assaf Schuster |
| 1996 | Reporting Red-Blue Intersections between Two Sets of Connected Line Segments. | Julien Basch, Leonidas J. Guibas, G. D. Ramkumar |
| 1996 | On-line Competive Algorithms for Call Admission in Optical Networks. | Baruch Awerbuch, Yossi Azar, Amos Fiat, Stefano Leonardi, Adi Rosn |
| 1996 | A New Approach to Optimal Planning of Robot Motion on a Tree with Obstacles. | Vincenzo Auletta, Domenico Parente, Giuseppe Persiano |
| 1996 | On Minimum-Area Hulls (Extended Abstract). | Esther M. Arkin, Yi-Jen Chiang, Martin Held, Joseph S. B. Mitchell, Vera Sacristn, Steven Skiena, Tae-Heng Yang |
| 1996 | Planar Spanners and Approximate Shortest Path Queries among Obstacles in the Plane. | Srinivasa Rao Arikati, Danny Z. Chen, L. Paul Chew, Gautam Das, Michiel H. M. Smid, Christos D. Zaroliagis |
| 1996 | Matching Convex Shapes with Respect to the Symmetric Difference. | Helmut Alt, Ulrich Fuchs, Gnter Rote, Gerald Weber |
| 1996 | On-line and Off-line Approximation Algorithms for Vector Covering Problems. | Noga Alon, Jnos Csirik, Sergey V. Sevastianov, Arjen P. A. Vestjens, Gerhard J. Woeginger |
| 1996 | Competive Analysis of Randomized Paging Algorithms. | Dimitris Achlioptas, Marek Chrobak, John Noga |
| 1995 | Approximation Algorithms for Feasible Cut and Multicut Problems. | Bo Yu, Joseph Cheriyan |
| 1995 | Load Balancing for Response Time. | Jeffery R. Westbrook |
| 1995 | Finding the Constrained Delaunay Triangulation and Constrainted Voronoi Diagram of a Simple Polygon in Linear-Time (Extended Abstract). | Cao An Wang, Francis Y. L. Chin |
| 1995 | An Efficient and Effective Approximation Algorithm for the Map Labeling Problem. | Frank Wagner, Alexander Wolff |
| 1995 | On Using q-Gram Locations in Approximate String Matching. | Erkki Sutinen, Jorma Tarhio |
| 1995 | On Parallel versus Sequential Approximation. | Maria J. Serna, Fatos Xhafa |
| 1995 | 0/1-Integer Programming: Optimization and Augmentation are Equivalent. | Andreas S. Schulz, Robert Weismantel, Gnter M. Ziegler |
| 1995 | The Binomial Transform and its Application to the Analysis of Skip Lists. | Patricio V. Poblete, J. Ian Munro, Thomas Papadakis |
| 1995 | Interval Graphs with Side (and Size) Constraints. | Itsik Pe'er, Ron Shamir |
| 1995 | Efficient Computation of the Geodesic Voronoi Diagram of Points in a Simple Polygon (Extended Abstract). | Evanthia Papadopoulou, D. T. Lee |
| 1995 | A Polyhedral Approach to Planar Augmentation and Related Problems. | Petra Mutzel |
| 1995 | On the All-Pairs Shortest Path Algorithm of Moffat and Takaoka. | Kurt Mehlhorn, Volker Priebe |