| 1999 | Fast Algorithms for Constructing Optimal Trees from Quartets. | David Bryant, Mike A. Steel |
| 1999 | Unscrambling Address Lines. | Andrei Z. Broder, Michael Mitzenmacher, Laurent Moll |
| 1999 | Stop Minding Your p's and q's: A Simplified | John M. Boyer, Wendy J. Myrvold |
| 1999 | A Formal Treatment of Remotely Keyed Encryption. | Matt Blaze, Joan Feigenbaum, Moni Naor |
| 1999 | Locked and Unlocked Polygonal Chains in 3D. | Therese Biedl, Erik D. Demaine, Martin L. Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Mark H. Overmars, Steve Robbins, Ileana Streinu, Godfried T. Toussaint, Sue Whitesides |
| 1999 | Efficient Algorithms for Petersen's Matching Theorem. | Therese C. Biedl, Prosenjit Bose, Erik D. Demaine, Anna Lubiw |
| 1999 | The Full Degree Spanning Tree Problem. | Randeep Bhatia, Samir Khuller, Robert Pless, Yoram J. Sussmann |
| 1999 | Queries with Segments in Voronoi Diagrams. | Sergei Bespamyatnikh, Jack Snoeyink |
| 1999 | A Wide-Range Efficient Algorithm for Minimal Triangulation. | Anne Berry |
| 1999 | Optimal Multichannel Communication Under Failure. | Tanya Y. Berger-Wolf, Edward M. Reingold |
| 1999 | Locally Efficient On-Line Strategies for Routing Packets Along Fixed Paths. | Petra Berenbrink, Christian Scheideler |
| 1999 | Finding Maximum Independent Sets in Sparse and General Graphs. | Richard Beigel |
| 1999 | Kinetic Collision Detection Between Two Simple Polygons. | Julien Basch, Jeff Erickson, Leonidas J. Guibas, John Hershberger, Li Zhang |
| 1999 | Fast, Fair, and Frugal Bandwidth Allocation in ATM Networks. | Yair Bartal, Martin Farach-Colton, Shibu Yooseph, Lisa Zhang |
| 1999 | Polygon-containment and Translational min-Hausdorff-Distance between segment Sets are 3SUM-hard. | Gill Barequet, Sariel Har-Peled |
| 1999 | Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions. | Gill Barequet, Sariel Har-Peled |
| 1999 | A Lower Bound for Hellbronn's Triangle Problem in | Gill Barequet |
| 1999 | Using Homogenous Weights for Approximating the Partial Cover Problem. | Reuven Bar-Yehuda |
| 1999 | Parameterized diff. | Brenda S. Baker |
| 1999 | Algorithms for Total Weighted Completion Time Scheduling. | Ivan D. Baev, Waleed Meleis, Alexandre E. Eichenberger |
| 1999 | Computing Morse Functions on Triangulated Manifolds. | Ulrike Axen |
| 1999 | Cooperative Sharing and Asynchronous Consensus Using Single-Reader Single-Writer Registers. | Yonatan Aumann, Avivit Kapah-Levy |
| 1999 | Group Signatures | Giuseppe Ateniese, Gene Tsudik |
| 1999 | Improved Bicriteria Existence Theorems for Scheduling. | Javed A. Aslam, April Rasala, Clifford Stein, Neal E. Young |
| 1999 | A Practical Clustering Algorithm for Static and Dynamic Information Organization. | Javed A. Aslam, Katya Pelekhov, Daniela Rus |