Paul S. Bonsma

Publication Activity (10 Years)

Years Active: 2002-2019
Publications (10 Years): 6

Top Topics

Subgraph Isomorphism

Lower And Upper Bounds

Top Venues

J. Discrete Algorithms

Publications

Paul S. Bonsma, Daniël Paulusma
Using contracted solution graphs for solving reconfiguration problems. Acta Informatica 56 (7-8) (2019)
Christoph Berkholz, Paul S. Bonsma, Martin Grohe
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement. Theory Comput. Syst. 60 (4) (2017)
Roberto Solis-Oba, Paul S. Bonsma, Stefanie Lowski
A 2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves. Algorithmica 77 (2) (2017)
Paul S. Bonsma
Rerouting shortest paths in planar graphs. Discret. Appl. Math. 231 (2017)
Paul S. Bonsma
Independent Set Reconfiguration in Cographs and their Generalizations. J. Graph Theory 83 (2) (2016)
Paul S. Bonsma, Daniël Paulusma
Using Contracted Solution Graphs for Solving Reconfiguration Problems. MFCS (2016)
Paul S. Bonsma, Daniël Paulusma
Using Contracted Solution Graphs for Solving Reconfiguration Problems. CoRR (2015)
Christoph Berkholz, Paul S. Bonsma, Martin Grohe
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement. CoRR (2015)
Paul S. Bonsma, Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman
The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration. IPEC (2014)
Paul S. Bonsma, Jens Schulz, Andreas Wiese
A Constant-Factor Approximation Algorithm for Unsplittable Flow on Paths. SIAM J. Comput. 43 (2) (2014)
Paul S. Bonsma, Amer E. Mouawad
The Complexity of Bounded Length Graph Recoloring. CoRR (2014)
Paul S. Bonsma
Independent Set Reconfiguration in Cographs. CoRR (2014)
Paul S. Bonsma, Marcin Kaminski, Marcin Wrochna
Reconfiguring Independent Sets in Claw-Free Graphs. SWAT (2014)
Paul S. Bonsma, Marcin Kaminski, Marcin Wrochna
Reconfiguring Independent Sets in Claw-Free Graphs. CoRR (2014)
Paul S. Bonsma
Independent Set Reconfiguration in Cographs. WG (2014)
Christoph Berkholz, Paul S. Bonsma, Martin Grohe
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement. ESA (2013)
Paul S. Bonsma
The complexity of rerouting shortest paths. Theor. Comput. Sci. 510 (2013)
Hans L. Bodlaender, Paul S. Bonsma, Daniel Lokshtanov
The Fine Details of Fast Dynamic Programming over Tree Decompositions. IPEC (2013)
Paul S. Bonsma
Rerouting shortest paths in planar graphs. FSTTCS (2012)
Paul S. Bonsma
Max-leaves spanning tree is APX-hard for cubic graphs. J. Discrete Algorithms 12 (2012)
Paul S. Bonsma, Felix Breuer
Counting Hexagonal Patches and Independent Sets in Circle Graphs. Algorithmica 63 (3) (2012)
Paul S. Bonsma, Florian Zickfeld
Improved bounds for spanning trees with many leaves. Discret. Math. 312 (6) (2012)
Paul S. Bonsma
The Complexity of Rerouting Shortest Paths. MFCS (2012)
Paul S. Bonsma, Arthur M. Farley, Andrzej Proskurowski
Extremal graphs having no matching cuts. J. Graph Theory 69 (2) (2012)
Paul S. Bonsma
Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces. STACS (2012)
Paul S. Bonsma, Hajo Broersma, Viresh Patel, Artem V. Pyatkin
The complexity of finding uniform sparsest cuts in various graph classes. J. Discrete Algorithms 14 (2012)
Paul S. Bonsma
Rerouting shortest paths in planar graphs CoRR (2012)
Paul S. Bonsma
Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces CoRR (2011)
Paul S. Bonsma, Jens Schulz, Andreas Wiese
A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths CoRR (2011)
Paul S. Bonsma, Daniel Lokshtanov
Feedback Vertex Set in Mixed Graphs. WADS (2011)
Paul S. Bonsma, Jens Schulz, Andreas Wiese
A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths. FOCS (2011)
Paul S. Bonsma, Florian Zickfeld
A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs. SIAM J. Discret. Math. 25 (4) (2011)
Paul S. Bonsma, Frederic Dorn
Tight bounds and a fast FPT algorithm for directed Max-Leaf Spanning Tree. ACM Trans. Algorithms 7 (4) (2011)
Paul S. Bonsma
Shortest Path Reconfiguration is PSPACE-hard CoRR (2010)
Paul S. Bonsma, Hajo Broersma, Viresh Patel, Artem V. Pyatkin
The Complexity Status of Problems Related to Sparsest Cuts. IWOCA (2010)
Paul S. Bonsma, Daniel Lokshtanov
Feedback Vertex Set in Mixed Graphs CoRR (2010)
Paul S. Bonsma
Most balanced minimum cuts. Discret. Appl. Math. 158 (4) (2010)
Paul S. Bonsma, Felix Breuer
Counting Hexagonal Patches and Independent Sets in Circle Graphs. LATIN (2010)
Paul S. Bonsma
Max-Leaves Spanning Tree is APX-hard for Cubic Graphs CoRR (2009)
Paul S. Bonsma, Felix Breuer
Finding Fullerene Patches in Polynomial Time CoRR (2009)
Paul S. Bonsma, Luis Cereceda
Finding Paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theor. Comput. Sci. 410 (50) (2009)
Paul S. Bonsma
The complexity of the matching-cut problem for planar graphs and other graph classes. J. Graph Theory 62 (2) (2009)
Paul S. Bonsma, Felix Breuer
Finding Fullerene Patches in Polynomial Time. ISAAC (2009)
Paul S. Bonsma
Spanning Trees with Many Leaves in Graphs With Minimum Degree Three. SIAM J. Discret. Math. 22 (3) (2008)
Paul S. Bonsma, Frederic Dorn
Tight Bounds and Faster Algorithms for Directed Max-Leaf Problems CoRR (2008)
Paul S. Bonsma, Florian Zickfeld
Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms. LATIN (2008)
Paul S. Bonsma, Felix Breuer
Finding Fullerene Patches in Polynomial Time I: Counting Hexagonal Patches CoRR (2008)
Paul S. Bonsma, Florian Zickfeld
A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs. WG (2008)
Paul S. Bonsma, Frederic Dorn
Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree. ESA (2008)
Paul S. Bonsma
Most balanced minimum cuts and partially ordered knapsack. CTW (2007)
Paul S. Bonsma, Luis Cereceda, Jan van den Heuvel, Matthew Johnson
Finding Paths between Graph Colourings: Computational Complexity and Possible Distances. Electron. Notes Discret. Math. 29 (2007)
Paul S. Bonsma
Linear time algorithms for finding sparsest cuts in various graph classes. Electron. Notes Discret. Math. 28 (2007)
Paul S. Bonsma, Frederic Dorn
An FPT Algorithm for Directed Spanning k-Leaf CoRR (2007)
Paul S. Bonsma, Luis Cereceda
Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances. MFCS (2007)
Paul S. Bonsma, Thomas Epping, Winfried Hochstättler
Complexity results on restricted instances of a paint shop problem for words. Discret. Appl. Math. 154 (9) (2006)
Paul S. Bonsma
Sparsest cuts and concurrent flows in product graphs. Discret. Appl. Math. 136 (2-3) (2004)
Paul S. Bonsma, Tobias Brüggemann, Gerhard J. Woeginger
A Faster FPT Algorithm for Finding Spanning Trees with Many Leaves. MFCS (2003)
Paul S. Bonsma
The Complexity of the Matching-Cut Problem for Planar Graphs and Other Graph Classes. WG (2003)
Paul S. Bonsma
The Complexity of the Matching-cut Problem for Various Graph Classes. Electron. Notes Discret. Math. 13 (2003)
Paul S. Bonsma, Nicola Ueffing, Lutz Volkmann
Edge-cuts leaving components of order at least three. Discret. Math. 256 (1-2) (2002)