Paul S. Bonsma

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

Collaborative distances:

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

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

Using Contracted Solution Graphs for Solving Reconfiguration Problems.

Paul S. Bonsma, Daniël Paulusma

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

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 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

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

Christoph Berkholz, Paul S. Bonsma, Martin Grohe

Proceedings of the Algorithms - ESA 2013, 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

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

The Complexity of Rerouting Shortest Paths.

Paul S. Bonsma

Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

Rerouting shortest paths in planar graphs.

Paul S. Bonsma

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

2011

Feedback Vertex Set in Mixed Graphs.

Paul S. Bonsma, Daniel Lokshtanov

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

A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths.

Paul S. Bonsma, Jens Schulz, Andreas Wiese

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

Most balanced minimum cuts.

Paul S. Bonsma

Discret. Appl. Math., 2010

Shortest Path Reconfiguration is PSPACE-hard

Paul S. Bonsma

CoRR, 2010

Counting Hexagonal Patches and Independent Sets in Circle Graphs.

Paul S. Bonsma, Felix Breuer

Proceedings of the LATIN 2010: Theoretical Informatics, 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 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

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

Paul S. Bonsma, Florian Zickfeld

Proceedings of the Graph-Theoretic Concepts in Computer Science, 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

Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree.

Paul S. Bonsma, Frederic Dorn

Proceedings of the Algorithms, 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

Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances.

Paul S. Bonsma, Luis Cereceda

Proceedings of the Mathematical Foundations of Computer Science 2007, 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

The Complexity of the Matching-Cut Problem for Planar Graphs and Other Graph Classes.

Paul S. Bonsma

Proceedings of the Graph-Theoretic Concepts in Computer Science, 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