| 1995 | Approximating the Bandwidth for Asteroidal Triple-Free Graphs. | Ton Kloks, Dieter Kratsch, Haiko Mller |
| 1995 | Fast Skeleton Construction. | Rolf Klein, Andrzej Lingas |
| 1995 | Beyond the Worst-Case Bisection Bound: Fast Sorting and Ranking on Meshes. | Michael Kaufmann, Jop F. Sibeyn, Torsten Suel |
| 1995 | The Online Transportation Problem. | Bala Kalyanasundaram, Kirk Pruhs |
| 1995 | Fully Dynamic Transitive Closure in Plane Dags with One Source and One Sink. | Thore Husfeldt |
| 1995 | Implementing Shared Memory on Mult-Dimensional Meshes and on the Fat-Tree (Extended Abstract). | Kieran T. Herley, Andrea Pietracaprina, Geppino Pucci |
| 1995 | Certificates and Fast Algorithms for Biconnectivity in Fully-Dynamic Graphs. | Monika Rauch Henzinger, Johannes A. La Poutr |
| 1995 | Routing with Bounded Buffers and Hot-Potato Routing in Vertex-Symmetric Networks. | Friedhelm Meyer auf der Heide, Christian Scheideler |
| 1995 | Maximum Skew-Symmetric Flows. | Andrew V. Goldberg, Alexander V. Karzanov |
| 1995 | Packing Trees. | Joseph Gil, Alon Itai |
| 1995 | Optimal Layouts on a Chain ATM Network (Extended Abstract). | Ornan Ori Gerstel, Avishai Wool, Shmuel Zaks |
| 1995 | Planarity for Clustered Graphs. | Qing-Wen Feng, Robert F. Cohen, Peter Eades |
| 1995 | Computing the Agreement of Trees with Bounded Degrees. | Martin Farach, Teresa M. Przytycka, Mikkel Thorup |
| 1995 | On Mixed Connectivity Certificates (Extended Abstract). | Shimon Even, Gene Itkis, Sergio Rajsbaum |
| 1995 | Near-Optimal Distributed Edge Coloring. | Devdatt P. Dubhashi, Alessandro Panconesi |
| 1995 | Sometimes Travelling is Easy: The Master Tour Problem. | Vladimir G. Deineko, Rdiger Rudolf, Gerhard J. Woeginger |
| 1995 | An Optimal Parallel Algorithm for Digital Curve Segmentation Using Hough Polygons and Monotone Function Search. | Peter Damaschke |
| 1995 | Shared Memory Simulations with Triple-Logarithmic Delay. | Artur Czumaj, Friedhelm Meyer auf der Heide, Volker Stemann |
| 1995 | Average Circuit Depth and Average Communication Complexity. | Bruno Codenotti, Peter Gemmell, Janos Simon |
| 1995 | A Geometric Approach to Betweenness. | Benny Chor, Madhu Sudan |
| 1995 | Fast Deterministic Simulation of Computations on Faulty Parallel Machines. | Bogdan S. Chlebus, Leszek Gasieniec, Andrzej Pelc |
| 1995 | Geometric Pattern Matching in d-Dimensional Space. | L. Paul Chew, Dorit Dor, Alon Efrat, Klara Kedem |
| 1995 | Optimal Parallel Shortest Paths in Small Treewidth Digraphs. | Shiva Chaudhuri, Christos D. Zaroliagis |
| 1995 | Self-Simulation for the Passive Optical Star Model. | Pascal Berthom, Th. Duboux, Torben Hagerup, Ilan Newman, Assaf Schuster |
| 1995 | The Centroid of Points with Approximate Weights. | Marshall W. Bern, David Eppstein, Leonidas J. Guibas, John Hershberger, Subhash Suri, Jan Wolter |