| 1996 | A Lower Bound for Nearly Minimal Adaptive and Hot Potato Algorithms. Ishai Ben-Aroya, Donald D. Chinn, Assaf Schuster |
| 1996 | A New Approach to Optimal Planning of Robot Motion on a Tree with Obstacles. Vincenzo Auletta, Domenico Parente, Giuseppe Persiano |
| 1996 | A New Regular Grammar Pattern Matching Algorithm. Bruce W. Watson |
| 1996 | A Unified Local Ratio Approximation of Node-Deletion Problems (Extended Abstract). Toshihiro Fujito |
| 1996 | Algorithms - ESA '96, Fourth Annual European Symposium, Barcelona, Spain, September 25-27, 1996, Proceedings Josep Díaz, Maria J. Serna |
| 1996 | Analysis of Shellsort and Related Algorithms. Robert Sedgewick |
| 1996 | Approximating the Unsatisfiability Threshold of Random Formulas (Extended Abstract). Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc |
| 1996 | Approximation Algorithms for Connected Dominating Sets. Sudipto Guha, Samir Khuller |
| 1996 | Approximation Algorithms for Dynamic Storage Allocations. Jordan Gergov |
| 1996 | Competive Analysis of Randomized Paging Algorithms. Dimitris Achlioptas, Marek Chrobak, John Noga |
| 1996 | Computational Aspacts of Organization Theory (Extended Abstract). Christos H. Papadimitriou |
| 1996 | Computing Upper and Lower Bounds on Textile Nesting Problems. Ralf Heckmann, Thomas Lengauer |
| 1996 | Drawing with Colors (Extended Abstract). Ashim Garg, Roberto Tamassia, Paola Vocca |
| 1996 | Efficient Dynamic Method-Lookup for Object Oriented Languages (Extended Abstract). Paolo Ferragina, S. Muthukrishnan |
| 1996 | Efficient Wavelength Routing on Directed Fiber Trees. Christos Kaklamanis, Giuseppe Persiano |
| 1996 | Fast Generation of Random Permutations via Networks Simulation. Artur Czumaj, Przemyslawa Kanarek, Miroslaw Kutylowski, Krzysztof Lorys |
| 1996 | Faster Algorithms for Subgraph Isomorphism of k-Connected Partial k-Trees. Anders Dessmark, Andrzej Lingas, Andrzej Proskurowski |
| 1996 | Generalized Streets Revisited. Alejandro López-Ortiz, Sven Schuierer |
| 1996 | Greedy Algorithms for the Shortest Common Superstring that are Asmtotically Optimal. Alan M. Frieze, Wojciech Szpankowski |
| 1996 | Lempel-Ziv Index for q-Grams. Juha Kärkkäinen, Erkki Sutinen |
| 1996 | Matching Convex Shapes with Respect to the Symmetric Difference. Helmut Alt, Ulrich Fuchs, Günter Rote, Gerald Weber |
| 1996 | Negative-Cycle Detection Algorithms. Boris V. Cherkassky, Andrew V. Goldberg |
| 1996 | On Minimum-Area Hulls (Extended Abstract). Esther M. Arkin, Yi-Jen Chiang, Martin Held, Joseph S. B. Mitchell, Vera Sacristán, Steven Skiena, Tae-Heng Yang |
| 1996 | On the Depth of Randomly Generated Circuits. Tatsuie Tsukiji, Fatos Xhafa |
| 1996 | On the Parallel Dynamic Dictionary Matching Problem: New Results with Applications. Paolo Ferragina, Fabrizio Luccio |
| 1996 | On-line Competive Algorithms for Call Admission in Optical Networks. Baruch Awerbuch, Yossi Azar, Amos Fiat, Stefano Leonardi, Adi Rosén |
| 1996 | On-line and Off-line Approximation Algorithms for Vector Covering Problems. Noga Alon, János Csirik, Sergey V. Sevastianov, Arjen P. A. Vestjens, Gerhard J. Woeginger |
| 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 | Parallel Complexity of Householder QR Factorization. Mauro Leoncini, Giovanni Manzini, Luciano Margara |
| 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 | Positive Linear Programming, Parallel Approximation and PCP's. Luca Trevisan |
| 1996 | Preemptive Weighted Completion Time Scheduling of Parallel Jobs. Uwe Schwiegelshohn |
| 1996 | Priority Queues: Small, Monotone and Trans-dichotomous. Rajeev Raman |
| 1996 | Race-Condition Detection in Parallel Computation with Semaphores (Extended Abstract). Philip N. Klein, Hsueh-I Lu, Robert H. B. Netzer |
| 1996 | Randomization of Search Trees by Subtree Size. Salvador Roura, Conrado Martínez |
| 1996 | Reporting Red-Blue Intersections between Two Sets of Connected Line Segments. Julien Basch, Leonidas J. Guibas, G. D. Ramkumar |
| 1996 | Scheduling Jobs with Communication Delays: Using Infeasible Solutions for Approximation (Extended Abstract). Rolf H. Möhring, Markus W. Schäffter, Andreas S. Schulz |
| 1996 | Simulated Annealing and Its Problems to Color Graphs. Andreas Nolte, Rainer Schrader |
| 1996 | The Analysis of Linear Probing Hashing with Buckets (Extended Abstract). Alfredo Viola, Patricio V. Poblete |
| 1996 | The Capacitated K-Center Problem (Extended Abstract). Samir Khuller, Yoram J. Sussmann |
| 1996 | The Structure of Circular Decomposable Metrics. George Christopher, Martin Farach, Michael A. Trick |