| 1995 | A Physical Model for the Satisfiability Problem. | Wenqui Huang, Wei Li, Weifeng Lu, Yuping Zhang |
| 1995 | Three Dimensional Weak Visibility: Complexity and Applications. | Cao An Wang, Binhai Zhu |
| 1995 | PFFM and Quasi-Morishima Matrices. | Hua Wang, Zhao-yong You |
| 1995 | Shortest Paths in Random Weighted Graphs. | Scott K. Walley, Harry H. Tan |
| 1995 | Primal-Dual Schema Based Approximation Algorithms (Abstract). | Vijay V. Vazirani |
| 1995 | Small Weight Bases for Hamming Codes. | John Tromp, Louxin Zhang, Ying Zhao |
| 1995 | Optimal Algorithms for Finding Connected Components of an Unknown Graph. | Weiping Shi, Douglas B. West |
| 1995 | Broadcasting in General Networks I: Trees. | Aditya Shastri |
| 1995 | Sets Computable in Polynomial Time on Average. | Rainer Schuler, Tomoyuki Yamakami |
| 1995 | Extending the Hong-Kung Model to Memory Hierarchies. | John E. Savage |
| 1995 | On Separating Proofs of Knowledge from Proofs of Membership of Languages and Its Application to Secure Identification Schemes (Extended Abstract). | Kouichi Sakurai |
| 1995 | Stack and Queue Number of 2-Trees. | S. Rengarajan, C. E. Veni Madhavan |
| 1995 | Improved Lower Bounds for the Randomized Boppana-Halldrsson Algorithm for MAXCLIQUE. | Marcus Peinado |
| 1995 | On Public-Key Cryptosystem Based on Church-Rosser String-Rewriting Systems (Extended Abstract). | Vladimir A. Oleshchuk |
| 1995 | Hamiltonian Cycles in 2-generated Cayley Digraphs of Abelian Groups. | Jixiang Meng |
| 1995 | Dense Packings of 3k(k+1)+1 Equal Disks in a Circle for k=1, 2, 3, 4 and 5. | Boris D. Lubachevsky, Ronald L. Graham |
| 1995 | An On-Line Algorithm for Some Uniform Processor Scheduling. | Rongheng Li, Lijie Shi |
| 1995 | A Highly Fault-Tolerant Quorum Consensus Method for Managing Replicated Data. | Xuemin Lin, Maria E. Orlowska |
| 1995 | Maximum Tree-Packing in Time O(n | Andrzej Lingas |
| 1995 | Set-Term Unification in a Logic Database Language. | Seung Jin Lim, Yiu-Kai Ng |
| 1995 | New Bound for Afine Resolvable Designs and Its Application to Authentication Codes. | Kaoru Kurosawa, Sanpei Kageyama |
| 1995 | Compact Location Problems with Budget and Communication Constraints. | Sven Oliver Krumke, Hartmut Noltemeier, S. S. Ravi, Madhav V. Marathe |
| 1995 | An Efficient Algorithm for Local Testability Problem of Finite State Automata. | Sam M. Kim, Robert McNaughton |
| 1995 | Rectangulating Rectilinear Polygons in Parallel. | Sung Kwon Kim |
| 1995 | An Exact Branch and Bound Algorithm for the Steiner Problem in Graphs. | B. N. Khoury, Panos M. Pardalos |