| 1995 | A Combinatorial Algorithm for Minimizing Symmetric Submodular Functions. Maurice Queyranne |
| 1995 | A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies when the Number of Character States is Fixed. Sampath Kannan, Tandy J. Warnow |
| 1995 | A New Way to Weigh Malnourished Euclidean Graphs. Gautam Das, Giri Narasimhan, Jeffrey S. Salowe |
| 1995 | Adapted Diameters and the Efficient Computation of Fourier Transforms on Finite Groups. David Keith Maslen, Daniel N. Rockmore |
| 1995 | Algorithms for Dynamic Closest Pair and n-Body Potential Fields. Paul B. Callahan, S. Rao Kosaraju |
| 1995 | Algorithms for Graphic Polymatroids and Parametric s-Sets. Harold N. Gabow |
| 1995 | Algorithms for the Optimal Loading of Recursive Neural Nets. Vijay Chandru, Abhi Dattasharma, S. Sathiya Keerthi, N. K. Sancheti, V. Vinay |
| 1995 | An Analysis of Some Heuristics for the Maximum Planar Subgraph Problem. Robert J. Cimikowski |
| 1995 | Approximating Discrete Collections via Local Improvements. Magnús M. Halldórsson |
| 1995 | Average Case Analysis of Dynamic Graph Algorithms. David Alberts, Monika Rauch Henzinger |
| 1995 | Average-Case Analysis of Off-Line and On-Line Knapsack Problems. George S. Lueker |
| 1995 | Broadcast in Radio Networks. Iris Gaber, Yishay Mansour |
| 1995 | Chaining Multiple-Alignment Fragments in Sub-Quadratic Time. Gene Myers, Webb Miller |
| 1995 | Characterizations of k-Terminal Flow Networks and Computing Network Flows in Partial k-Trees. Torben Hagerup, Jyrki Katajainen, Naomi Nishimura, Prabhakar Ragde |
| 1995 | Circular Separability of Polygon. Jean-Daniel Boissonnat, Jurek Czyzowicz, Olivier Devillers, Mariette Yvinec |
| 1995 | Computing a Minimum-Weight k-Link Path in Graphs with the Concave Monge Property. Baruch Schieber |
| 1995 | Computing the Local Consensus of Trees. Sampath Kannan, Tandy J. Warnow, Shibu Yooseph |
| 1995 | Counting and Random Generation of Strings in Regular Languages. Sampath Kannan, Z. Sweedyk, Stephen R. Mahaney |
| 1995 | David P. Williamson: An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems. R. Ravi |
| 1995 | Design of Practical and Provably Good Random Number Generators (Extended Abstract). William Aiello, Sivaramakrishnan Rajagopalan, Ramarathnam Venkatesan |
| 1995 | Dihedral Bounds for Mesh Generation in High Dimensions. Marshall W. Bern, L. Paul Chew, David Eppstein, Jim Ruppert |
| 1995 | Doing Two-Level Logic Minimization 100 Times Faster. Olivier Coudert |
| 1995 | Efficient Parallel Computations for Singular Band Matrices. Wayne Eberly |
| 1995 | External-Memory Graph Algorithms. Yi-Jen Chiang, Michael T. Goodrich, Edward F. Grove, Roberto Tamassia, Darren Erik Vengroff, Jeffrey Scott Vitter |
| 1995 | Fairness in Scheduling. Miklós Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J. Schulman, Orli Waarts |
| 1995 | Fast Approximation Algorithm for Minimum Cost Multicommodity Flow. Anil Kamath, Omri Palmon, Serge A. Plotkin |
| 1995 | Fast Deterministic Approximation for the Multicommodity Flow Problem. Tomasz Radzik |
| 1995 | Fast Incremental Text Editing. Paolo Ferragina, Roberto Grossi |
| 1995 | Finding Optimal Edge-Rankings of Trees. Xiao Zhou, Takao Nishizeki |
| 1995 | Finding Subsets Maximizing Minimum Structures. Magnús M. Halldórsson, Kazuo Iwano, Naoki Katoh, Takeshi Tokuyama |
| 1995 | From Valid Inequalities to Heuristics: A Unified View of Primal-Dual Approximation Algorithms in Covering Problems. Dimitris Bertsimas, Chung-Piaw Teo |
| 1995 | Graph Isomorphism Testing without Numberics for Graphs of Bounded Eigenvalue Multiplicity. Martin Fürer |
| 1995 | Greedy Dynamic Routing on Arrays. Nabil Kahalé, Frank Thomson Leighton |
| 1995 | Guaranteeing Fair Service to Persistent Dependent Tasks. Amotz Bar-Noy, Alain J. Mayer, Baruch Schieber, Madhu Sudan |
| 1995 | Improved Algorithms for Protein Motif Recognition. Bonnie Berger, David Bruce Wilson |
| 1995 | Improved Bounds for All Optical Routing. Yonatan Aumann, Yuval Rabani |
| 1995 | Improved Interior Point Algorithms for Exact and Approximate Solution of Multicommodity Flow Problems. Anil Kamath, Omri Palmon |
| 1995 | Improved Randomized On-Line Algorithms for the List Update Problem. Susanne Albers |
| 1995 | Localizing a Robot with Minimum Travel. Gregory Dudek, Kathleen Romanik, Sue Whitesides |
| 1995 | Locally Orientable Graphs, Cell Structures, and a New Algorithm for the Incremental Maintenance of Connectivity Carcasses. Yefim Dinitz, Alek Vainshtein |
| 1995 | Lower Bounds for Identifying Subset Members with Subset Queries. Emanuel Knill |
| 1995 | Lower Bounds for Linear Satisfiability Problems. Jeff Erickson |
| 1995 | Morphing Binary Trees. John Hershberger, Subhash Suri |
| 1995 | Multiple Translational Containment: Approximate and Exact Algorithms. Karen L. Daniels, Victor Milenkovic |
| 1995 | Of Mice and Men: Algorithms for Evolutionary Distances Between Genomes with Translocation. John D. Kececioglu, R. Ravi |
| 1995 | On Algorithm Design for Metrical Task Systems. William R. Burley, Sandy Irani |
| 1995 | On the All-Pairs Euclidean Short Path Problem. Danny Z. Chen |
| 1995 | On the Entropy of DNA: Algorithms and Measurements Based on Memory and Rapid Convergence. Martin Farach, Michiel O. Noordewier, Serap A. Savari, Larry A. Shepp, Aaron D. Wyner, Jacob Ziv |
| 1995 | On the Performance of Spectral Graph Partitioning Methods. Stephen Guattery, Gary L. Miller |
| 1995 | On the Statistical Dependencies of Coalesced Hashing and Their Implications for Both Full and Limited Independence. Alan Siegel |
| 1995 | On-line Approximate List Indexing with Applications. Arne Andersson, Ola Petersson |
| 1995 | Online Bin Packing with Lookahead. Edward F. Grove |
| 1995 | Optimal One-Way Sorting on a One-Dimensional Sub-Bus Array. James D. Fix, Richard E. Ladner |
| 1995 | Output-Sensitive Construction of Polytopes in Four Dimensions and Clipped Voronoi Diagrams in Three. Timothy M. Chan, Jack Snoeyink, Chee-Keng Yap |
| 1995 | Parameterized Pattern Matching by Boyer-Moore-Type Algorithms. Brenda S. Baker |
| 1995 | Path Optimization and Near-Greedy Analysis for Graph Partitioning: An Empirical Study. Jonathan W. Berry, Mark K. Goldberg |
| 1995 | Polynomial Methods for Separable Convex Optimization in Unimodular Spaces. Alexander V. Karzanov, S. Thomas McCormick |
| 1995 | Practical Methods for Approximating Shortest Paths on a Convex Polytope in R John Hershberger, Subhash Suri |
| 1995 | Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 22-24 January 1995. San Francisco, California, USA. Kenneth L. Clarkson |
| 1995 | Randomized Rounding Without Solving the Linear Program. Neal E. Young |
| 1995 | Register Allocation in Structured Programs. Sampath Kannan, Todd A. Proebsting |
| 1995 | Selecting the Median. Dorit Dor, Uri Zwick |
| 1995 | Sorting Permutations by Transpositions. Vineet Bafna, Pavel A. Pevzner |
| 1995 | Splay Trees for Data Compression. Dennis Grinberg, Sivaramakrishnan Rajagopalan, Ramarathnam Venkatesan, Victor K. Wei |
| 1995 | Subgraph Isomorphism in Planar Graphs and Related Problems. David Eppstein |
| 1995 | The P-range Tree: A New Data Structure for Range Searching in Secondary Memory. Sairam Subramanian, Sridhar Ramaswamy |
| 1995 | The Quickest Transshipment Problem. Bruce Hoppe, Éva Tardos |
| 1995 | The Statistical Adversary Allows Optimal Money-Making Trading Strategies. Andrew Chou, Jeremy R. Cooperstock, Ran El-Yaniv, Michael Klugerman, Frank Thomson Leighton |
| 1995 | Trustee-based Tracing Extensions to Anonymous Cash and the Making of Anonymous Change. Ernest F. Brickell, Peter Gemmell, David W. Kravitz |
| 1995 | Using Network Flows for Surface Modeling. Rolf H. Möhring, Matthias Müller-Hannemann, Karsten Weihe |
| 1995 | Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions. L. Paul Chew, Klara Kedem, Micha Sharir, Boaz Tagansky, Emo Welzl |