21 citations · 25 across the 5 of their papers we have counts for
5 papers
Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width
Petr A. Golovach, Pinar Heggernes, Mamadou Moustapha Kanté +3
The linear induced matching width (LMIM-width) of a graph is a width parameter defined by using the notion of branch-decompositions of a set function on ternary trees. In this pape…
Solving Hamiltonian Cycle by an EPT Algorithm for a Non-sparse Parameter
Sigve Hortemo Sæther
Many hard graph problems, such as Hamiltonian Cycle, become FPT when parameterized by treewidth, a parameter that is bounded only on sparse graphs. When parameterized by the more g…
Between Treewidth and Clique-width
Sigve Hortemo Sæther, Jan Arne Telle
Many hard graph problems can be solved efficiently when restricted to graphs of bounded treewidth, and more generally to graphs of bounded clique-width. But there is a price to be…
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…