| 1995 | Greedy Approximations of Independent Sets in Low Degree Graphs. | Magns M. Halldrsson, Kiyohito Yoshihara |
| 1995 | finding Smallest Supertrees. | Arvind Gupta, Naomi Nishimura |
| 1995 | Orders of Gauss Periods in Finite Fields. | Joachim von zur Gathen, Igor E. Shparlinski |
| 1995 | A Resource Assignment Problem on Graphs. | Satoshi Fujita, Tiko Kameda, Masafumi Yamashita |
| 1995 | Linear matching-time algorithm for the directed graph isomorphism problem. | James Jianghai Fu |
| 1995 | Two Arc Disjoint Paths in Eulerian Diagraphs. | Andrs Frank, Toshihide Ibaraki, Hiroshi Nagamochi |
| 1995 | More Efficient Parallel Flow Algorithms. | Jrgen Dedorath, Jordan Gergov, Torben Hagerup |
| 1995 | Competitive Searching in Polygons - Beyond Generalised Streets. | Amitava Datta, Christoph A. Hipke, Sven Schuierer |
| 1995 | Searching for a Monotone Function by Independent Threshold Queries. | Peter Damaschke |
| 1995 | Practical Logic (Abstract). | John N. Crossley |
| 1995 | Finding the Medial Axis of a Simple Polygon in Linear Time. | Francis Y. L. Chin, Jack Snoeyink, Cao An Wang |
| 1995 | Some Geometric Lower Bounds. | Hank Chien, William L. Steiger |
| 1995 | A Fast Algorithm for Computing Optimal Rectilinear Steiner Trees for Extremal Point Sets. | Siu-Wing Cheng, Chi-Keung Tang |
| 1995 | NC Algorithms for Partitioning Sparse Graphs into Induced Forests with an Application. | Zhi-Zhong Chen |
| 1995 | Weighted Domination on Cocomparability Graphs. | Maw-Shang Chang |
| 1995 | Linear-time In-place Selection in Less than 3n Comparisons. | Svante Carlsson, Mikael Sundstrm |
| 1995 | Heap Construction: Optimal in Both Worst and Average Cases? | Svante Carlsson, Jingsen Chen |
| 1995 | Matching Nuts and Bolts Faster. | Phillip G. Bradford, Rudolf Fleischer |
| 1995 | No Quadrangulation is Extremely Odd. | Prosenjit Bose, Godfried T. Toussaint |
| 1995 | Computing in Linear Time a Chord from Which a Simple Polygon is Weakly Internally Visible. | Binay K. Bhattacharya, Asish Mukhopadhyay |
| 1995 | Constant Ratio Approximations of the Weighted Feedback Vertex Set Problem for Undirected Graphs. | Vineet Bafna, Piotr Berman, Toshihiro Fujito |
| 1995 | Finding Dense Subgraphs. | Yuichi Asahiro, Kazuo Iwama |
| 1995 | The I/O - Complexity of Ordered Binary - Decision Diagram Manipulation. | Lars Arge |
| 1995 | The Parallel Complexity of Approximating the High Degree Subgraph Problem. | Alexander E. Andreev, Andrea Clementi, Pierluigi Crescenzi, Elias Dahlhaus, Sergio De Agostino, Jos D. P. Rolim |
| 1995 | Illumination with Orthogonal Floodlights. | James Abello, Vladimir Estivill-Castro, Thomas C. Shermer, Jorge Urrutia |