| 1996 | Efficient Union-Find for Planar Graphs and other Sparse Graph Classes (Extended Abstract). | Jens Gustedt |
| 1996 | LexBFS-Orderings and Power of Graphs. | Feodor F. Dragan, Falk Nicolai, Andreas Brandstdt |
| 1996 | On-Line Algorithms for Shortest Path Problems on Planar Digraphs. | Hristo N. Djidjev |
| 1996 | System Diagnosis with Smallest Risk of Error. | Krzysztof Diks, Andrzej Pelc |
| 1996 | More General Parallel Tree Contraction: Register Allocation and Broadcasting in a Tree. | Krzysztof Diks, Torben Hagerup |
| 1996 | Upward Drawings of Search Trees (Extended Abstract). | Pierluigi Crescenzi, Paolo Penna |
| 1996 | Closure Properties of Context-Tree Hyperedge Replacement Systems. | Ornella Ciotti, Francesco Parisi-Presicce |
| 1996 | Counting Edges in a Dag. | Serafino Cicerone, Daniele Frigioni, Umberto Nanni, Francesco Pugliese |
| 1996 | Optimal Parallel Routing in Star Graphs. | Chi-Chang Chen, Jianer Chen |
| 1996 | Clique and Anticlique Partition of Graphs. | Krzysztof Brys, Zbigniew Lonc |
| 1996 | Embedding Complete Binary Trees in Product Graphs. | Adrienne L. Broadwater, Kemal Efe, Antonio Fernndez |
| 1996 | On k-Partitioning the n-Cube. | Sergei L. Bezrukov |
| 1996 | Node Rewriting in Hypergraphs. | Michel Bauderon, Hlne Jacquet |
| 1996 | A New Characterization of P4-connected Graphs. | Luitpold Babel, Stephan Olariu |
| 1996 | Improved Approximations of Independent Dominating Set in Bounded Degree Graphs. | Paola Alimonti, Tiziana Calamoneri |
| 1995 | Highly Fault-Tolerant Routings and Diameter Vulnerability for Generalized Hypercube Graphs. | Koichi Wada, Takaharu Ikeo, Kimio Kawaguchi, Wei Chen |
| 1995 | Sub-Cubic Cost Algorithms for the All Pairs Shortest Path Problem. | Tadao Takaoka |
| 1995 | An Approximation Algorithm for 3-Colourability. | Ingo Schiermeyer |
| 1995 | Optimal Cutwidths and Bisection Widths of 2- and 3-Dimensional Meshes. | Jos D. P. Rolim, Ondrej Skora, Imrich Vrto |
| 1995 | On Termination of Graph Rewriting. | Detlef Plump |
| 1995 | Partition Coefficients of Acyclic Graphs. | John L. Pfaltz |
| 1995 | Complexity and Approximability of Certain Bicriteria Location Problems. | Sven Oliver Krumke, Hartmut Noltemeier, S. S. Ravi, Madhav V. Marathe |
| 1995 | VC-Dimensions for Graphs (Extended Abstract). | Evangelos Kranakis, Danny Krizanc, Berthold Ruf, Jorge Urrutia, Gerhard J. Woeginger |
| 1995 | Finding and Counting Small Induced Subgraphs Efficiently. | Ton Kloks, Dieter Kratsch, Haiko Mller |
| 1995 | Hot-Potato Routing on Multi-Dimensional Tori. | Friedhelm Meyer auf der Heide, Matthias Westermann |