66 citations · 206 across the 36 of their papers we have counts for
6 papers · 1 filter
Myhill-Nerode methods for hypergraphs
René van Bevern, Rodney G. Downey, Michael R. Fellows +2
We give an analog of the Myhill-Nerode methods from formal language theory for hypergraphs and use it to derive the following results for two NP-hard hypergraph problems: * We prov…
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…
From edge-disjoint paths to independent paths
Serge Gaspers
Let f(k) denote the maximum such that every simple undirected graph containing two vertices s,t and k edge-disjoint s-t paths, also contains two vertices u,v and f(k) independent u…
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…