58 citations · 327 across the 60 of their papers we have counts for
6 papers · 2 filters
Parameterized Complexity and Kernel Bounds for Hard Planning Problems
Christer Bäckström, Peter Jonsson, Sebastian Ordyniak +1
The propositional planning problem is a notoriously difficult computational problem. Downey et al. (1999) initiated the parameterized analysis of planning (with plan length as the…
Don't Be Strict in Local Search!
Serge Gaspers, Eun Jung Kim, Sebastian Ordyniak +2
Local Search is one of the fundamental approaches to combinatorial optimization and it is used throughout AI. Several local search algorithms are based on searching the k-exchange…
On Finding Optimal Polytrees
Serge Gaspers, Mikko Koivisto, Mathieu Liedloff +2
Inferring probabilistic networks from data is a notoriously difficult task. Under various goodness-of-fit measures, finding an optimal network is NP-hard, even if restricted to pol…
Strong Backdoors to Bounded Treewidth SAT
Serge Gaspers, Stefan Szeider
There are various approaches to exploiting "hidden structure" in instances of hard combinatorial problems to allow faster algorithms than for general unstructured or random instanc…
Strong Backdoors to Nested Satisfiability
Serge Gaspers, Stefan Szeider
Knuth (1990) introduced the class of nested formulas and showed that their satisfiability can be decided in polynomial time. We show that, parameterized by the size of a smallest s…
Computing Resolution-Path Dependencies in Linear Time
Friedrich Slivovsky, Stefan Szeider
The alternation of existential and universal quantifiers in a quantified boolean formula (QBF) generates dependencies among variables that must be respected when evaluating the for…