| 1991 | A Fast Algorithm for Connecting Grid Points to the Boundary with Nonintersecting Straight Lines. Yitzhak Birk, Jeffrey B. Lotspiech |
| 1991 | A New Lower Bound Technique and Its Application: Tight Lower Bound for a Polygon Triangulation Problem. Prakash V. Ramanan |
| 1991 | A Sublinear-Time Randomized Parallel Algorithm for the Maximum Clique Problem in Perfect Graphs. Farid Alizadeh |
| 1991 | Adaptive Heuristics for Binary Search Trees and Constant Linkage Cost. Tony W. Lai, Derick Wood |
| 1991 | Algorithms and Complexity Analysis for Some Flow Problems. Edith Cohen, Nimrod Megiddo |
| 1991 | An Efficient Parallel Algorithm for the Row Minima of a Totally Monotone Matrix. Mikhail J. Atallah, S. Rao Kosaraju |
| 1991 | An O(n Tze-Heng Ma, Jeremy P. Spinrad |
| 1991 | Approximating the Number of Zeroes of a GF[2] Polynomial. Marek Karpinski, Michael Luby |
| 1991 | Approximation Algorithms for Planar Traveling Salesman Tours and Minimum-Length Triangulations. Kenneth L. Clarkson |
| 1991 | Bounded Space On-Line Bin Packing: Best is Better than First. János Csirik, David S. Johnson |
| 1991 | Circular Hulls and Orbiforms of Simple Polygons. V. Chandru, R. Venkataraman |
| 1991 | Complexity Results and Algorithms for { <, <=, = }-Constrained Scheduling. Bonnie Berger, Lenore Cowen |
| 1991 | Computing a Face in an Arrangement of Line Segments. Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, Jack Snoeyink |
| 1991 | Decomposing Graphs into Regions of Small Diameter. Nathan Linial, Michael E. Saks |
| 1991 | Density Graphs and Separators. Gary L. Miller, Stephen A. Vavasis |
| 1991 | Dynamic Expression Trees and their Applications (Extended Abstract). Robert F. Cohen, Roberto Tamassia |
| 1991 | Edge Coloring Planar Graphs with Two Outerplanar Subgraphs. Lenwood S. Heath |
| 1991 | Efficient 2-dimensional Approximate Matching of Non-Rectangular Figures. Amihood Amir, Martin Farach |
| 1991 | Efficient Sequential and Parallel Algorithms for Computing Recovery Points in Trees and Paths. Marek Chrobak, David Eppstein, Giuseppe F. Italiano, Moti Yung |
| 1991 | Fast Hashing on a PRAM - Designing by Expectation. Joseph Gil, Yossi Matias |
| 1991 | Finding Stabbing Lines in 3-Dimensional Space. Marco Pellegrini, Peter W. Shor |
| 1991 | Fully Persistent Lists with Catenation. James R. Driscoll, Daniel Dominic Sleator, Robert Endre Tarjan |
| 1991 | Improved Approximation Algorithms for Shop Scheduling Problems. David B. Shmoys, Clifford Stein, Joel Wein |
| 1991 | Learning the Fourier Spectrum of Probabilistic Lists and Trees. William Aiello, Milena Mihail |
| 1991 | Maintaining the Minimal Distance of a Point Set in Polylogarithmic Time. Michiel H. M. Smid |
| 1991 | Matching Points into Noise Regions: Combinatorial Bounds and Algorithms. Esther M. Arkin, Klara Kedem, Joseph S. B. Mitchell, Josef Sprinzak, Michael Werman |
| 1991 | Offline Maintenance of Planar Configurations. John Hershberger, Subhash Suri |
| 1991 | On Finding Minimal 2-Connected Subgraphs. Pierre Kelsen, Vijaya Ramachandran |
| 1991 | On Partitions and Presortedness of Sequences. Jingsen Chen, Svante Carlsson |
| 1991 | On the Parallel Complexity of Evaluating Game Trees. Andrei Z. Broder, Anna R. Karlin, Prabhakar Raghavan, Eli Upfal |
| 1991 | On-Line Caching as Cache Size Varies. Neal E. Young |
| 1991 | On-Line Weighted Matching. Bala Kalyanasundaram, Kirk Pruhs |
| 1991 | Optimal Algorithms for Tree Partitioning. Greg N. Frederickson |
| 1991 | Optimal Time Randomized Consensus - Making Resilient Algorithms Fast in Practice. Michael E. Saks, Nir Shavit, Heather Woll |
| 1991 | Parallel Complexity of Tridiagonal Symmetric Eigenvalue Problem. Dario Bini, Victor Y. Pan |
| 1991 | Persistence, Amortization and Randomization. Paul F. Dietz, Rajeev Raman |
| 1991 | Planar Geometric Location Problems and Maintaining the Width of a Planar Set. Pankaj K. Agarwal, Micha Sharir |
| 1991 | Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 28-30 January 1991, San Francisco, California, USA. Alok Aggarwal |
| 1991 | Randomized Competitive Algorithms for the List Update Problem. Sandy Irani, Nick Reingold, Jeffery R. Westbrook, Daniel Dominic Sleator |
| 1991 | Recognizing Strong Connectivity in (Dynamic) Periodic Graphs and its Relation to Integer Programming. Murali S. Kodialam, James B. Orlin |
| 1991 | Routing through a Dense Channel with Minimum Total Wire Length. Michael Formann, Dorothea Wagner, Frank Wagner |
| 1991 | Space-efficient Ray-shooting and Intersection Searching: Algorithms, Dynamization, and Applications. Siu-Wing Cheng, Ravi Janardan |
| 1991 | The Analysis of Multidimensional Searching in Quad-Trees. Philippe Flajolet, Gaston H. Gonnet, Claude Puech, J. M. Robson |
| 1991 | The Aquarium Keeper's Problem. Jurek Czyzowicz, Peter Egyed, Hazel Everett, David Rappaport, Thomas C. Shermer, Diane L. Souvaine, Godfried T. Toussaint, Jorge Urrutia |
| 1991 | The Canadian Traveller Problem. Amotz Bar-Noy, Baruch Schieber |
| 1991 | The First Classical Ramsey Number for Hypergraphs is Computed. Brendan D. McKay, Stanislaw P. Radziszowski |
| 1991 | The Fourth Moment Method. Bonnie Berger |
| 1991 | Tight Bounds for On-Line Tree Embeddings. Sandeep N. Bhatt, David S. Greenberg, Frank Thomson Leighton, Pangfeng Liu |
| 1991 | Tight Bounds on the Complexity of the Boyer-Moore String Matching Algorithm. Richard Cole |
| 1991 | Tight Bounds on the Number of Minimum-Mean Cycle Cancellations and Related Results. Tomasz Radzik, Andrew V. Goldberg |
| 1991 | Time-Work Tradeoffs for Parallel Graph Algorithms. Thomas H. Spencer |
| 1991 | Triangulating Three-Colored Graphs. Sampath Kannan, Tandy J. Warnow |
| 1991 | Ultra-Fast Expected Time Parallel Algorithms. Philip D. MacKenzie, Quentin F. Stout |
| 1991 | Upward Planar Drawing of Single Source Acyclic Digraphs. Michael D. Hutton, Anna Lubiw |