Paul S. Bonsma

  • University of Twente, Faculty of Electrical Engineering, Mathematics and Computer Science
  • Humboldt University Berlin, Computer Science Department

According to our database1, Paul S. Bonsma authored at least 40 papers between 2002 and 2019.

Collaborative distances:



In proceedings 
PhD thesis 


Online presence:



Using contracted solution graphs for solving reconfiguration problems.
Acta Informatica, 2019

Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement.
Theory Comput. Syst., 2017

Rerouting shortest paths in planar graphs.
Discret. Appl. Math., 2017

A 2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves.
Algorithmica, 2017

Independent Set Reconfiguration in Cographs and their Generalizations.
J. Graph Theory, 2016

A Constant-Factor Approximation Algorithm for Unsplittable Flow on Paths.
SIAM J. Comput., 2014

The Complexity of Bounded Length Graph Recoloring.
CoRR, 2014

Independent Set Reconfiguration in Cographs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2014

Reconfiguring Independent Sets in Claw-Free Graphs.
Proceedings of the Algorithm Theory - SWAT 2014, 2014

The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration.
Proceedings of the Parameterized and Exact Computation - 9th International Symposium, 2014

The complexity of rerouting shortest paths.
Theor. Comput. Sci., 2013

The Fine Details of Fast Dynamic Programming over Tree Decompositions.
Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

Extremal graphs having no matching cuts.
J. Graph Theory, 2012

The complexity of finding uniform sparsest cuts in various graph classes.
J. Discrete Algorithms, 2012

Max-leaves spanning tree is APX-hard for cubic graphs.
J. Discrete Algorithms, 2012

Improved bounds for spanning trees with many leaves.
Discret. Math., 2012

Counting Hexagonal Patches and Independent Sets in Circle Graphs.
Algorithmica, 2012

Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces.
Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

Tight bounds and a fast FPT algorithm for directed Max-Leaf Spanning Tree.
ACM Trans. Algorithms, 2011

A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs.
SIAM J. Discret. Math., 2011

Feedback Vertex Set in Mixed Graphs.
Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

Most balanced minimum cuts.
Discret. Appl. Math., 2010

Shortest Path Reconfiguration is PSPACE-hard
CoRR, 2010

The Complexity Status of Problems Related to Sparsest Cuts.
Proceedings of the Combinatorial Algorithms - 21st International Workshop, 2010

Finding Paths between graph colourings: PSPACE-completeness and superpolynomial distances.
Theor. Comput. Sci., 2009

The complexity of the matching-cut problem for planar graphs and other graph classes.
J. Graph Theory, 2009

Finding Fullerene Patches in Polynomial Time.
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

Spanning Trees with Many Leaves in Graphs With Minimum Degree Three.
SIAM J. Discret. Math., 2008

Finding Fullerene Patches in Polynomial Time I: Counting Hexagonal Patches
CoRR, 2008

Tight Bounds and Faster Algorithms for Directed Max-Leaf Problems
CoRR, 2008

Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms.
Proceedings of the LATIN 2008: Theoretical Informatics, 2008

Finding Paths between Graph Colourings: Computational Complexity and Possible Distances.
Electron. Notes Discret. Math., 2007

Linear time algorithms for finding sparsest cuts in various graph classes.
Electron. Notes Discret. Math., 2007

An FPT Algorithm for Directed Spanning k-Leaf
CoRR, 2007

Most balanced minimum cuts and partially ordered knapsack.
Proceedings of the Sixth Cologne Twente Workshop on Graphs and Combinatorial Optimization, 2007

Complexity results on restricted instances of a paint shop problem for words.
Discret. Appl. Math., 2006

Sparsest cuts and concurrent flows in product graphs.
Discret. Appl. Math., 2004

The Complexity of the Matching-cut Problem for Various Graph Classes.
Electron. Notes Discret. Math., 2003

A Faster FPT Algorithm for Finding Spanning Trees with Many Leaves.
Proceedings of the Mathematical Foundations of Computer Science 2003, 2003

Edge-cuts leaving components of order at least three.
Discret. Math., 2002