| 1995 | A Linear Algorithm for the Maximal Planar Subgraph Problem. Hristo N. Djidjev |
| 1995 | A Linear-time Construction of the Relative Neighborhood Graph within a Histogram. Andrzej Lingas, Asish Mukhopadhyay |
| 1995 | A Ranking Algorithm for Hamilton Paths in Shuffle-Exchange Graphs. Fred S. Annexstein, Eugene A. Kuchko |
| 1995 | A Simpler Minimum Spanning Tree Verification Algorithm. Valerie King |
| 1995 | Algorithmic Arguments in Physics of Computation. Paul M. B. Vitányi, Ming Li |
| 1995 | Algorithms and Data Structures, 4th International Workshop, WADS '95, Kingston, Ontario, Canada, August 16-18, 1995, Proceedings Selim G. Akl, Frank K. H. A. Dehne, Jörg-Rüdiger Sack, Nicola Santoro |
| 1995 | Amortization Results for Chromatic Search Trees, with an Application to Priority Queues. Joan Boyar, Rolf Fagerberg, Kim S. Larsen |
| 1995 | Approximation of Constraint Satisfaction via Local Search (Extended Abstract). Hoong Chuin Lau |
| 1995 | Arrangements in Higher Dimensions: Voronoi Diagrams, Motion Planning, and Other Applications. Micha Sharir |
| 1995 | Balanced Distributed Search Trees Do Not Exist. Brigitte Kröll, Peter Widmayer |
| 1995 | Competitive Algorithms for the On-line Traveling Salesman. Giorgio Ausiello, Esteban Feuerstein, Stefano Leonardi, Leen Stougie, Maurizio Talamo |
| 1995 | Computing Common Tangents Without a Separating Line. David G. Kirkpatrick, Jack Snoeyink |
| 1995 | Computing Proximity Drawings of Trees in the 3-Dimemsional Space. Giuseppe Liotta, Giuseppe Di Battista |
| 1995 | Computing a Dominating Pair in an Asteroidal Triple-free Graph in Linear Time. Derek G. Corneil, Stephan Olariu, Lorna Stewart |
| 1995 | Computing a Shortest Watchman Path in a Simple Polygon in Polynomial-Time. Svante Carlsson, Håkan Jonsson |
| 1995 | Dynamic Algorithms for the Dyck Languages. Gudmund Skovbjerg Frandsen, Thore Husfeldt, Peter Bro Miltersen, Theis Rauhe, Søren Skyum |
| 1995 | Efficient Geometric Algorithms for Workpiece Orientation in 4- and 5-Axis NC-Machining. Prosenjit Gupta, Ravi Janardan, Jayanth Majhi, Tony C. Woo |
| 1995 | Experiences with the Implementation of Geometric Algorithms (Abstract). Kurt Mehlhorn |
| 1995 | Experiments on the Practical I/O Efficiency of Geometric Algorithms: Distribution Sweep vs. Plane Sweep. Yi-Jen Chiang |
| 1995 | Fast Meldable Priority Queues. Gerth Stølting Brodal |
| 1995 | Faster Enumeration of All Spanning Trees of a Directed Graph. Ramesh Hariharan, Sanjiv Kapoor, Vijay Kumar |
| 1995 | Going Home Through an Unknown Street. Alejandro López-Ortiz, Sven Schuierer |
| 1995 | Improved Length Bounds for the Shortest Superstring Problem (Extended Abstract). Chris Armen, Clifford Stein |
| 1995 | In-Place Calculation of Minimum-Redundancy Codes. Alistair Moffat, Jyrki Katajainen |
| 1995 | Load Balancing in Quorum Systems (Extended Abstract). Ron Holzman, Yosi Marcus, David Peleg |
| 1995 | Lower Bounds to Processor-Time Tradeoffs under Bounded-Speed Message Propagation. Gianfranco Bilardi, Franco P. Preparata |
| 1995 | Non-Overlapping Local Alignments (Weighted Independent Sets of Axis Parallel Rectangles). Vineet Bafna, Babu O. Narayanan, R. Ravi |
| 1995 | Obstructions to Within a Few Vertices or Edges of Acyclic. Kevin Cattell, Michael J. Dinneen, Michael R. Fellows |
| 1995 | On Some Geometric Selection and Optimization Problems via Sorted Matrices. Alex Glozman, Klara Kedem, Gregory Shpitalnik |
| 1995 | On the Approximation Properties of Independent Set Problem in Degree 3 Graphs. Piotr Berman, Toshihiro Fujito |
| 1995 | On the Complexity of Approximating and Illuminating Three-Dimensional Convex Polyhedra (Preliminary Version). Gautam Das, Michael T. Goodrich |
| 1995 | On the Computation of Fast Data Transmissions in Networks with Capacities and Delays. Dimitrios Kagaris, Spyros Tragoudas, Grammati E. Pantziou, Christos D. Zaroliagis |
| 1995 | On the Difficulty of Range Searching. Arne Andersson, Kurt Swanson |
| 1995 | Online Perfect Matching and Mobile Computing. Edward F. Grove, Ming-Yang Kao, P. Krishnan, Jeffrey Scott Vitter |
| 1995 | Page Migration with Limited Local Memory Capacity. Susanne Albers, Hisashi Koga |
| 1995 | Quadrangulations of Planar Sets. Godfried T. Toussaint |
| 1995 | Randomized Algorithms for Metrical Task Systems. Sandy Irani, Steven S. Seiden |
| 1995 | Regular-Factors In The Complements Of Partial k-Trees. Damon Kaller, Arvind Gupta, Thomas C. Shermer |
| 1995 | Routing on Trees via Matchings. Alan Roberts, Antonios Symvonis, Louxin Zhang |
| 1995 | Routing with Delays when Storage is Costly. Sanjoy K. Sanjoy, Gara Pruesse |
| 1995 | Scheduling Jobs that Arrive Over Time (Extended Abstract). Cynthia A. Phillips, Clifford Stein, Joel Wein |
| 1995 | Tables Should Be Sorted (On Random Access Machines). Faith E. Fich, Peter Bro Miltersen |
| 1995 | The Buffer Tree: A New Technique for Optimal I/O-Algorithms (Extended Abstract). Lars Arge |
| 1995 | The Two-Line Center Problem from a Polar View: A New Algorithm and Data Structure. Jerzy W. Jaromczyk, Miroslaw Kowaluk |
| 1995 | Topology B-Trees and Their Applications. Paul B. Callahan, Michael T. Goodrich, Kumar Ramaiyer |
| 1995 | Two-Floodlight Illumination of Convex Polygons. Vladimir Estivill-Castro, Jorge Urrutia |