16 citations · 52 across the 11 of their papers we have counts for
16 papers
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
Christoph Berkholz, Paul Bonsma, Martin Grohe
An assignment of colours to the vertices of a graph is stable if any two vertices of the same colour have identically coloured neighbourhoods. The goal of colour refinement is to f…
Using Contracted Solution Graphs for Solving Reconfiguration Problems
Paul Bonsma, Daniel Paulusma
We introduce in a general setting a dynamic programming method for solving reconfiguration problems. Our method is based on contracted solution graphs, which are obtained from solu…
The Complexity of Bounded Length Graph Recoloring
Paul Bonsma, Amer E. Mouawad
We study the following question: Given are two -colorings and of a graph on vertices, and integer . The question is whether can be modified into , b…
Reconfiguring Independent Sets in Claw-Free Graphs
Paul Bonsma, Marcin Kamiński, Marcin Wrochna
We present a polynomial-time algorithm that, given two independent sets in a claw-free graph , decides whether one can be transformed into the other by a sequence of elementary…
Independent Set Reconfiguration in Cographs
Paul Bonsma
We study the following independent set reconfiguration problem, called TAR-Reachability: given two independent sets and of a graph , both of size at least , is it pos…
Rerouting shortest paths in planar graphs
Paul Bonsma
A rerouting sequence is a sequence of shortest st-paths such that consecutive paths differ in one vertex. We study the the Shortest Path Rerouting Problem, which asks, given two sh…