| 1996 | Positive Linear Programming, Parallel Approximation and PCP's. | Luca Trevisan |
| 1996 | Analysis of Shellsort and Related Algorithms. | Robert Sedgewick |
| 1996 | Preemptive Weighted Completion Time Scheduling of Parallel Jobs. | Uwe Schwiegelshohn |
| 1996 | Randomization of Search Trees by Subtree Size. | Salvador Roura, Conrado Martnez |
| 1996 | Priority Queues: Small, Monotone and Trans-dichotomous. | Rajeev Raman |
| 1996 | Computational Aspacts of Organization Theory (Extended Abstract). | Christos H. Papadimitriou |
| 1996 | Simulated Annealing and Its Problems to Color Graphs. | Andreas Nolte, Rainer Schrader |
| 1996 | Scheduling Jobs with Communication Delays: Using Infeasible Solutions for Approximation (Extended Abstract). | Rolf H. Mhring, Markus W. Schffter, Andreas S. Schulz |
| 1996 | Generalized Streets Revisited. | Alejandro Lpez-Ortiz, Sven Schuierer |
| 1996 | Parallel Complexity of Householder QR Factorization. | Mauro Leoncini, Giovanni Manzini, Luciano Margara |
| 1996 | Race-Condition Detection in Parallel Computation with Semaphores (Extended Abstract). | Philip N. Klein, Hsueh-I Lu, Robert H. B. Netzer |
| 1996 | Approximating the Unsatisfiability Threshold of Random Formulas (Extended Abstract). | Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc |
| 1996 | The Capacitated K-Center Problem (Extended Abstract). | Samir Khuller, Yoram J. Sussmann |
| 1996 | Lempel-Ziv Index for q-Grams. | Juha Krkkinen, Erkki Sutinen |
| 1996 | Efficient Wavelength Routing on Directed Fiber Trees. | Christos Kaklamanis, Giuseppe Persiano |
| 1996 | Computing Upper and Lower Bounds on Textile Nesting Problems. | Ralf Heckmann, Thomas Lengauer |
| 1996 | Approximation Algorithms for Connected Dominating Sets. | Sudipto Guha, Samir Khuller |
| 1996 | Approximation Algorithms for Dynamic Storage Allocations. | Jordan Gergov |
| 1996 | Drawing with Colors (Extended Abstract). | Ashim Garg, Roberto Tamassia, Paola Vocca |
| 1996 | A Unified Local Ratio Approximation of Node-Deletion Problems (Extended Abstract). | Toshihiro Fujito |
| 1996 | Greedy Algorithms for the Shortest Common Superstring that are Asmtotically Optimal. | Alan M. Frieze, Wojciech Szpankowski |
| 1996 | Efficient Dynamic Method-Lookup for Object Oriented Languages (Extended Abstract). | Paolo Ferragina, S. Muthukrishnan |
| 1996 | On the Parallel Dynamic Dictionary Matching Problem: New Results with Applications. | Paolo Ferragina, Fabrizio Luccio |
| 1996 | Faster Algorithms for Subgraph Isomorphism of k-Connected Partial k-Trees. | Anders Dessmark, Andrzej Lingas, Andrzej Proskurowski |
| 1996 | Fast Generation of Random Permutations via Networks Simulation. | Artur Czumaj, Przemyslawa Kanarek, Miroslaw Kutylowski, Krzysztof Lorys |