| 2016 | MFCS | Using Contracted Solution Graphs for Solving Reconfiguration Problems. | Paul S. Bonsma, Danil Paulusma |
| 2014 | WG | Independent Set Reconfiguration in Cographs. | Paul S. Bonsma |
| 2013 | ESA | Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement. | Christoph Berkholz, Paul S. Bonsma, Martin Grohe |
| 2012 | MFCS | The Complexity of Rerouting Shortest Paths. | Paul S. Bonsma |
| 2012 | STACS | Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces. | Paul S. Bonsma |
| 2011 | FOCS | A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths. | Paul S. Bonsma, Jens Schulz, Andreas Wiese |
| 2011 | WADS | Feedback Vertex Set in Mixed Graphs. | Paul S. Bonsma, Daniel Lokshtanov |
| 2010 | IWOCA | The Complexity Status of Problems Related to Sparsest Cuts. | Paul S. Bonsma, Hajo Broersma, Viresh Patel, Artem V. Pyatkin |
| 2010 | LATIN | Counting Hexagonal Patches and Independent Sets in Circle Graphs. | Paul S. Bonsma, Felix Breuer |
| 2009 | ISAAC | Finding Fullerene Patches in Polynomial Time. | Paul S. Bonsma, Felix Breuer |
| 2008 | ESA | Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree. | Paul S. Bonsma, Frederic Dorn |
| 2008 | LATIN | Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms. | Paul S. Bonsma, Florian Zickfeld |
| 2008 | WG | A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs. | Paul S. Bonsma, Florian Zickfeld |
| 2007 | MFCS | Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances. | Paul S. Bonsma, Luis Cereceda |
| 2003 | MFCS | A Faster FPT Algorithm for Finding Spanning Trees with Many Leaves. | Paul S. Bonsma, Tobias Brggemann, Gerhard J. Woeginger |
| 2003 | WG | The Complexity of the Matching-Cut Problem for Planar Graphs and Other Graph Classes. | Paul S. Bonsma |