Paul S. Bonsma

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

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2019

Using contracted solution graphs for solving reconfiguration problems.

Paul S. Bonsma, Daniël Paulusma

Acta Informatica, 2019

2017

Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement.

Christoph Berkholz, Paul S. Bonsma, Martin Grohe

Theory Comput. Syst., 2017

Rerouting shortest paths in planar graphs.

Paul S. Bonsma

Discret. Appl. Math., 2017

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

Roberto Solis-Oba, Paul S. Bonsma, Stefanie Lowski

Algorithmica, 2017

2016

Independent Set Reconfiguration in Cographs and their Generalizations.

Paul S. Bonsma

J. Graph Theory, 2016

2014

A Constant-Factor Approximation Algorithm for Unsplittable Flow on Paths.

Paul S. Bonsma, Jens Schulz, Andreas Wiese

SIAM J. Comput., 2014

The Complexity of Bounded Length Graph Recoloring.

Paul S. Bonsma, Amer E. Mouawad

CoRR, 2014

Independent Set Reconfiguration in Cographs.

Paul S. Bonsma

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2014

Reconfiguring Independent Sets in Claw-Free Graphs.

Paul S. Bonsma, Marcin Kaminski, Marcin Wrochna

Proceedings of the Algorithm Theory - SWAT 2014, 2014

The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration.

Paul S. Bonsma, Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman

Proceedings of the Parameterized and Exact Computation - 9th International Symposium, 2014

2013

The complexity of rerouting shortest paths.

Paul S. Bonsma

Theor. Comput. Sci., 2013

The Fine Details of Fast Dynamic Programming over Tree Decompositions.

Hans L. Bodlaender, Paul S. Bonsma, Daniel Lokshtanov

Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

2012

Extremal graphs having no matching cuts.

Paul S. Bonsma, Arthur M. Farley, Andrzej Proskurowski

J. Graph Theory, 2012

The complexity of finding uniform sparsest cuts in various graph classes.

Paul S. Bonsma, Hajo Broersma, Viresh Patel, Artem V. Pyatkin

J. Discrete Algorithms, 2012

Max-leaves spanning tree is APX-hard for cubic graphs.

Paul S. Bonsma

J. Discrete Algorithms, 2012

Improved bounds for spanning trees with many leaves.

Paul S. Bonsma, Florian Zickfeld

Discret. Math., 2012

Counting Hexagonal Patches and Independent Sets in Circle Graphs.

Paul S. Bonsma, Felix Breuer

Algorithmica, 2012

Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces.

Paul S. Bonsma

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

2011

Tight bounds and a fast FPT algorithm for directed Max-Leaf Spanning Tree.

Paul S. Bonsma, Frederic Dorn

ACM Trans. Algorithms, 2011

A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs.

Paul S. Bonsma, Florian Zickfeld

SIAM J. Discret. Math., 2011

Feedback Vertex Set in Mixed Graphs.

Paul S. Bonsma, Daniel Lokshtanov

Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

2010

Most balanced minimum cuts.

Paul S. Bonsma

Discret. Appl. Math., 2010

Shortest Path Reconfiguration is PSPACE-hard

Paul S. Bonsma

CoRR, 2010

The Complexity Status of Problems Related to Sparsest Cuts.

Paul S. Bonsma, Hajo Broersma, Viresh Patel, Artem V. Pyatkin

Proceedings of the Combinatorial Algorithms - 21st International Workshop, 2010

2009

Finding Paths between graph colourings: PSPACE-completeness and superpolynomial distances.

Paul S. Bonsma, Luis Cereceda

Theor. Comput. Sci., 2009

The complexity of the matching-cut problem for planar graphs and other graph classes.

Paul S. Bonsma

J. Graph Theory, 2009

Finding Fullerene Patches in Polynomial Time.

Paul S. Bonsma, Felix Breuer

Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

2008

Spanning Trees with Many Leaves in Graphs With Minimum Degree Three.

Paul S. Bonsma

SIAM J. Discret. Math., 2008

Finding Fullerene Patches in Polynomial Time I: Counting Hexagonal Patches

Paul S. Bonsma, Felix Breuer

CoRR, 2008

Tight Bounds and Faster Algorithms for Directed Max-Leaf Problems

Paul S. Bonsma, Frederic Dorn

CoRR, 2008

Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms.

Paul S. Bonsma, Florian Zickfeld

Proceedings of the LATIN 2008: Theoretical Informatics, 2008

2007

Finding Paths between Graph Colourings: Computational Complexity and Possible Distances.

Paul S. Bonsma, Luis Cereceda, Jan van den Heuvel, Matthew Johnson

Electron. Notes Discret. Math., 2007

Linear time algorithms for finding sparsest cuts in various graph classes.

Paul S. Bonsma

Electron. Notes Discret. Math., 2007

An FPT Algorithm for Directed Spanning k-Leaf

Paul S. Bonsma, Frederic Dorn

CoRR, 2007

Most balanced minimum cuts and partially ordered knapsack.

Paul S. Bonsma

Proceedings of the Sixth Cologne Twente Workshop on Graphs and Combinatorial Optimization, 2007

2006

Complexity results on restricted instances of a paint shop problem for words.

Paul S. Bonsma, Thomas Epping, Winfried Hochstättler

Discret. Appl. Math., 2006

2004

Sparsest cuts and concurrent flows in product graphs.

Paul S. Bonsma

Discret. Appl. Math., 2004

2003

The Complexity of the Matching-cut Problem for Various Graph Classes.

Paul S. Bonsma

Electron. Notes Discret. Math., 2003

A Faster FPT Algorithm for Finding Spanning Trees with Many Leaves.

Paul S. Bonsma, Tobias Brüggemann, Gerhard J. Woeginger

Proceedings of the Mathematical Foundations of Computer Science 2003, 2003

2002

Edge-cuts leaving components of order at least three.

Paul S. Bonsma, Nicola Ueffing, Lutz Volkmann

Discret. Math., 2002