| 1996 | A Better Approximation Algorithm for Finding Planar Subgraphs. Gruia Calinescu, Cristina G. Fernandes, Ulrich Finkler, Howard J. Karloff |
| 1996 | A Capacity Scaling Algorithm for Convex Cost Submodular Flows. Satoru Iwata |
| 1996 | A Commercial Application of Survivable Network Design: ITP/INPLANS CCS Network Topology Analyzer. Milena Mihail, David Shallcross, Nate Dean, Marco Mostrel |
| 1996 | A New Approach to Parallel Computation of Polynomial GCD and to Related Parallel Computations over Fields and Integer Rings. Victor Y. Pan |
| 1996 | A Polynomial Algorithm for Abstract Maximum Flow. S. Thomas McCormick |
| 1996 | A Polynomial Time Primal Network Simplex Algorithm for Minimum Cost Flows (An Extended Abstract). James B. Orlin |
| 1996 | An Efficient Algorithm for the Vertex-Disjoint Paths Problem in Random Graphs. Andrei Z. Broder, Alan M. Frieze, Stephen Suen, Eli Upfal |
| 1996 | An Empirical Study of Dynamic Graph Algorithms (Extended Abstract). David Alberts, Giuseppe Cattaneo, Giuseppe F. Italiano |
| 1996 | An Extension of the Lovász Local Lemma, and its Applications to Integer Programming. Aravind Srinivasan |
| 1996 | An Improved Approximation Ratio for the Minimum Latency Problem. Michel X. Goemans, Jon M. Kleinberg |
| 1996 | An O(log* n) Approximation Algorithm for the Asymmetric p-Center Problem. Sundar Vishwanathan |
| 1996 | An O(n log n) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees. Richard Cole, Ramesh Hariharan |
| 1996 | Analysis of Practical Backoff Protocols for Contention Resolution with Multiple Servers. Leslie Ann Goldberg, Philip D. MacKenzie |
| 1996 | Approximation Algorithms for Curvature-Constrained Shortest Paths. Hongyan Wang, Pankaj K. Agarwal |
| 1996 | Asymptotic Experimental Analysis for the Held-Karp Traveling Salesman Bound. David S. Johnson, Lyle A. McGeoch, Edward E. Rothberg |
| 1996 | Best-Fit Bin-Packing with Random Order. Claire Kenyon |
| 1996 | Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing (Preliminary Version). Claire Kenyon, Yuval Rabani, Alistair Sinclair |
| 1996 | Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology. Monika Rauch Henzinger, Valerie King, Tandy J. Warnow |
| 1996 | Data Collection for the Sloan Digital Sky Survey - A Network-Flow Heuristic. Robert Lupton, F. Miller Maley, Neal E. Young |
| 1996 | Depth Optimal Sorting Networks Resistant to k Passive Faults. Marek Piotrów |
| 1996 | Distributed Paging for General Networks. Baruch Awerbuch, Yair Bartal, Amos Fiat |
| 1996 | Efficient Generation of k-Directional Assembly Sequences. Pankaj K. Agarwal, Mark de Berg, Dan Halperin, Micha Sharir |
| 1996 | Efficient Suffix Trees on Secondary Storage (extended Abstract). David R. Clark, J. Ian Munro |
| 1996 | Electrostatic Fields without Singularities: Theory and Algorithms. Marco Pellegrini |
| 1996 | Error-Resilient DNA Computation. Richard M. Karp, Claire Kenyon, Orli Waarts |
| 1996 | Fast Estimation of Diameter and Shortest Paths (without Matrix Multiplication). Donald Aingworth, Chandra Chekuri, Rajeev Motwani |
| 1996 | Fast String Searching in Secondary Storage: Theoretical Developments And Experimental Results. Paolo Ferragina, Roberto Grossi |
| 1996 | Fixed-Dimensional Parallel Linesr Programming via epsilon-Relative-Approximations. Michael T. Goodrich |
| 1996 | Fully Dynamic Output Bounded Single Source Shortest Path Problem (Extended Abstract). Daniele Frigioni, Alberto Marchetti-Spaccamela, Umberto Nanni |
| 1996 | Games, Computers, and O.R. Ehud Kalai |
| 1996 | Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple New Method for the Geometric k-MST Problem. Joseph S. B. Mitchell |
| 1996 | How to Get an Exact Sample From a Generic Markov Chain and Sample a Random Spanning Tree From a Directed Graph, Both Within the Cover Time. David Bruce Wilson, James Gary Propp |
| 1996 | Improving Biconnectivity Approximation via Local Optimization. Ka Wong Chong, Tak Wah Lam |
| 1996 | Increasing the Weight of Minimum Spanning Trees. Greg N. Frederickson, Roberto Solis-Oba |
| 1996 | Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications. Ming-Deh A. Huang, Ashwin J. Rao |
| 1996 | Isomorphism Testing and Display of Symmetries in Dynamic Trees. Siu-Wing Cheng, Moon-Pun Ng |
| 1996 | Limit Theorems for Minimum-Weight Triangulations, Other Euclidean Functionals, and Probabilistic Recurrence Relations (Extended Abstract). Mordecai J. Golin |
| 1996 | Matching Nuts and Bolts in O(n log n) Time (Extended Abstract). János Komlós, Yuan Ma, Endre Szemerédi |
| 1996 | Multiplicative Equations over Commuting Matrices. László Babai, Robert Beals, Jin-Yi Cai, Gábor Ivanyos, Eugene M. Luks |
| 1996 | Multiprocessor Scheduling with Rejection. Yair Bartal, Stefano Leonardi, Alberto Marchetti-Spaccamela, Jirí Sgall, Leen Stougie |
| 1996 | On Certificates and Lookahead in Dynamic Graph Problems. Sanjeev Khanna, Rajeev Motwani, Randall H. Wilson |
| 1996 | On RAM Priority Queues. Mikkel Thorup |
| 1996 | On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics). Richa Agarwala, Vineet Bafna, Martin Farach, Babu O. Narayanan, Mike Paterson, Mikkel Thorup |
| 1996 | On-line Generalized Steiner Problem. Baruch Awerbuch, Yossi Azar, Yair Bartal |
| 1996 | Optimal Placement of Convex Polygons to Maximize Point Containment. Matthew Dickerson, Daniel Scharstein |
| 1996 | Optimal randomized EREW PRAM Algorithms for Finding Spanning Forests and for other Basic Graph Connectivity Problems. Shay Halperin, Uri Zwick |
| 1996 | Optimization Problems Related to Zigzag Pocket Machining (Extended Abstract). Esther M. Arkin, Martin Held, Christopher L. Smith |
| 1996 | Perfect Arborescence Packing in Preflow Mincut Graphs. Harold N. Gabow |
| 1996 | Polynomial-Time Solutions to Image Segmentation. Tetsuo Asano, Danny Z. Chen, Naoki Katoh, Takeshi Tokuyama |
| 1996 | Preemptive Scheduling of Parallel Jobs on Multiprocessors. Xiaotie Deng, Nian Gu, Tim Brecht, Kaicheng Lu |
| 1996 | Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 28-30 January 1996, Atlanta, Georgia, USA. Éva Tardos |
| 1996 | Quasi-Greedy Triangulations Approximating the Minimum Weight Triangulation. Christos Levcopoulos, Drago Krznaric |
| 1996 | RNC Algorithms for the Uniform Generation of Combinatorial Structures. Michele Zito, Ida Pu, Martyn Amos, Alan Gibbons |
| 1996 | Randomized Robot Navigation Algorithms. Piotr Berman, Avrim Blum, Amos Fiat, Howard J. Karloff, Adi Rosén, Michael E. Saks |
| 1996 | Reconstructing the Evolutionary History of Natural Languages. Tandy J. Warnow, Donald Ringe, Ann Taylor |
| 1996 | Routing and Admission Control in General Topology Networks with Poisson Arrivals. Anil Kamath, Omri Palmon, Serge A. Plotkin |
| 1996 | Scheduling to Minimize Average Completion Time: Off-line and On-line Algorithms. Leslie A. Hall, David B. Shmoys, Joel Wein |
| 1996 | Scheduling with Conflicts, and Applications to Traffic Signal Control. Sandy Irani, Vitus J. Leung |
| 1996 | Selecting Training Inputs via Greedy Rank Covering. Adam L. Buchsbaum, Jan P. H. van Santen |
| 1996 | Self-Stabilizing Algorithms for Synchronous Unidirectional Rings. Alain J. Mayer, Rafail Ostrovsky, Moti Yung |
| 1996 | Sequential and Parallel Subquadratic Work Algorithms for Constructing Approximately Optimal Binary Search Trees. Marek Karpinski, Lawrence L. Larmore, Wojciech Rytter |
| 1996 | The Complexity of Flat Origami. Marshall W. Bern, Barry Hayes |
| 1996 | Tiling a Figure Using a Height in a Tree. Eric Rémila |
| 1996 | Time and Space Efficient Method-Lookup for Object-Oriented Programs (Extended Abstract). S. Muthukrishnan, Martin Müller |
| 1996 | To Cut... or Not to Cut (Applications of Comparative Physical Maps in Molecular Evolution). Sridhar Hannenhalli, Pavel A. Pevzner |
| 1996 | Worst-Case Efficient Priority Queues. Gerth Stølting Brodal |