D. Paulusma

activity

20092026

most citedSatisfiability of Acyclic and Almost Acyclic CNF Formulas

38 citations · 246 across the 68 of their papers we have counts for

collaborators

Showing 2015 · cs.DSShow all

3 papers · 2 filters

cs.DS2015

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…

cs.DS2015

Editing to a Planar Graph of Given Degrees

Konrad K. Dabrowski, Petr A. Golovach, Pim van 't Hof +2

We consider the following graph modification problem. Let the input consist of a graph $G = (V, E)$ , a weight function $w : V \cup E \to N$ , a cost function $c\colo…

cs.DS2015

Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs

Konrad K. Dabrowski, Francois Dross, Matthew Johnson +1

A colouring of a graph $G = (V, E)$ is a function $c : V \to {1, 2, \dots}$ such that $c (u) \neq = c (v)$ for every $uv \in E$ . A $k$ -regular list assignment of $G$ is a function $L…