Paul Bonsma

Available identifiers

zbMath Open bonsma.paul-sMaRDI QIDQ392172

List of research outcomes

Publication	Date of Publication	Type
Using contracted solution graphs for solving reconfiguration problems	2019-10-17	Paper
Using contracted solution graphs for solving reconfiguration problems.	2018-03-21	Paper
Rerouting shortest paths in planar graphs	2017-09-12	Paper
Tight lower and upper bounds for the complexity of canonical colour refinement	2017-08-15	Paper
A 2-approximation algorithm for finding a spanning tree with maximum number of leaves	2017-03-03	Paper
https://portal.mardi4nfdi.de/entity/Q2957511	2017-01-26	Paper
Independent Set Reconfiguration in Cographs and their Generalizations	2016-10-13	Paper
The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration	2015-09-15	Paper
Independent Set Reconfiguration in Cographs	2015-09-09	Paper
Tight bounds and a fast FPT algorithm for directed Max-Leaf Spanning Tree	2014-09-09	Paper
Reconfiguring Independent Sets in Claw-Free Graphs	2014-09-02	Paper
A Constant-Factor Approximation Algorithm for Unsplittable Flow on Paths	2014-07-30	Paper
A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths	2014-07-30	Paper
The complexity of rerouting shortest paths	2014-01-13	Paper
The Fine Details of Fast Dynamic Programming over Tree Decompositions	2013-12-10	Paper
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement	2013-09-17	Paper
The Complexity of Rerouting Shortest Paths	2012-09-25	Paper
The complexity of finding uniform sparsest cuts in various graph classes	2012-09-13	Paper
https://portal.mardi4nfdi.de/entity/Q2904791	2012-08-23	Paper
Max-leaves spanning tree is APX-hard for cubic graphs	2012-05-11	Paper
Counting hexagonal patches and independent sets in circle graphs	2012-04-26	Paper
Improved bounds for spanning trees with many leaves	2012-04-13	Paper
A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs	2012-03-15	Paper
Extremal graphs having no matching cuts	2012-02-08	Paper
Feedback Vertex Set in Mixed Graphs	2011-08-12	Paper
The Complexity Status of Problems Related to Sparsest Cuts	2011-05-19	Paper
https://portal.mardi4nfdi.de/entity/Q3576676	2010-07-30	Paper
Most balanced minimum cuts	2010-05-05	Paper
Counting Hexagonal Patches and Independent Sets in Circle Graphs	2010-04-27	Paper
Graph-Theoretic Concepts in Computer Science	2010-01-12	Paper
The complexity of the matching-cut problem for planar graphs and other graph classes	2009-12-18	Paper
Finding Fullerene Patches in Polynomial Time	2009-12-17	Paper
Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances	2009-11-06	Paper
Spanning Trees with Many Leaves in Graphs With Minimum Degree Three	2009-08-20	Paper
A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs	2009-01-20	Paper
Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree	2008-11-25	Paper
Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances	2008-09-17	Paper
Finding Paths between Graph Colourings: Computational Complexity and Possible Distances	2008-06-05	Paper
Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms	2008-04-15	Paper
Mathematical Foundations of Computer Science 2003	2007-12-07	Paper
Linear time algorithms for finding sparsest cuts in various graph classes	2007-05-29	Paper
Complexity results on restricted instances of a paint shop problem for words	2006-06-09	Paper
https://portal.mardi4nfdi.de/entity/Q5708527	2005-11-18	Paper
Sparsest cuts and concurrent flows in product graphs.	2004-03-14	Paper
Edge-cuts leaving components of order at least three	2002-12-02	Paper

Research outcomes over time

Doctoral students

No records found.

Known relations from the MaRDI Knowledge Graph

Property	Value
MaRDI profile type	MaRDI person profile
instance of	human

This page was built for person: Paul Bonsma