Paul S. Bonsma

60 papers A* 1A 3B 13C 2Journal 39Unranked 2

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