21 citations · 31 across the 6 of their papers we have counts for
7 papers
Recognition of Linear and Star Variants of Leaf Powers is in P
Benjamin Bergougnoux, Svein Høgemo, Jan Arne Telle +1
A -leaf power of a tree is a graph whose vertices are the leaves of and whose edges connect pairs of leaves whose distance in is at most . A graph is a leaf p…
Fast Dynamic Programming on Graph Decompositions
Johan M. M. van Rooij, Hans L. Bodlaender, Erik Jan van Leeuwen +2
In this paper, we consider tree decompositions, branch decompositions, and clique decompositions. We improve the running time of dynamic programming algorithms on these graph decom…
Solving MaxSAT and #SAT on structured CNF formulas
Sigve Hortemo Sæther, Jan Arne Telle, Martin Vatshelle
In this paper we propose a structural parameter of CNF formulas and use it to identify instances of weighted MaxSAT and #SAT that can be solved in polynomial time. Given a CNF form…
Faster Algorithms For Vertex Partitioning Problems Parameterized by Clique-width
Sang-il Oum, Sigve Hortemo Sæther, Martin Vatshelle
Many NP-hard problems, such as Dominating Set, are FPT parameterized by clique-width. For graphs of clique-width given with a -expression, Dominating Set can be solved in $4…
k-Gap Interval Graphs
Fedor V. Fomin, Serge Gaspers, Petr Golovach +5
We initiate the study of a new parameterization of graph problems. In a multiple interval representation of a graph, each vertex is associated to at least one interval of the real…
On graph classes with logarithmic boolean-width
Rémy Belmonte, Martin Vatshelle
Boolean-width is a recently introduced graph parameter. Many problems are fixed parameter tractable when parametrized by boolean-width, for instance "Minimum Weighted Dominating Se…
Fast FPT algorithms for vertex subset and vertex partitioning problems using neighborhood unions
B. -M. Bui-Xuan, J. A. Telle, M. Vatshelle
We introduce the graph parameter boolean-width, related to the number of different unions of neighborhoods across a cut of a graph. Boolean-width is similar to rank-width, which is…