6 citations · 27 across the 25 of their papers we have counts for
Showing 2014Show all
2 papers · 1 filter
cs.DS2014
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…
cs.DS2014★ 2 cited
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…