16 citations · 52 across the 11 of their papers we have counts for
7 papers · 1 filter
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…
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…
A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths
Paul Bonsma, Jens Schulz, Andreas Wiese
In the unsplittable flow problem on a path, we are given a capacitated path and tasks, each task having a demand, a profit, and start and end vertices. The goal is to compu…
Feedback Vertex Set in Mixed Graphs
Paul Bonsma, Daniel Lokshtanov
A mixed graph is a graph with both directed and undirected edges. We present an algorithm for deciding whether a given mixed graph on vertices contains a feedback vertex set (F…
Tight Bounds and Faster Algorithms for Directed Max-Leaf Problems
Paul Bonsma, Frederic Dorn
An out-tree of a directed graph is a rooted tree subgraph with all arcs directed outwards from the root. An out-branching is a spanning out-tree. By and we…