8 citations · 21 across the 12 of their papers we have counts for
10 papers · 1 filter
From FPT Decision to FPT Enumeration
Nadia Creignou, Timo Camillo Merkl, Reinhard Pichler +1
Fixed-parameter tractable (FPT) algorithms have been successfully applied to many intractable problems -- with a focus on decision and optimization problems. Their aim is to confin…
Complexity of Reasoning with Cardinality Minimality Conditions
Nadia Creignou, Frédéric Olive, Johannes Schmidt
Many AI-related reasoning problems are based on the problem of satisfiability of propositional formulas with some cardinality-minimality condition. While the complexity of the sati…
Enumeration Classes Defined by Circuits
Nadia Creignou, Arnaud Durand, Heribert Vollmer
We refine the complexity landscape for enumeration problems by introducing very low classes defined by using Boolean circuits as enumerators. We locate well-known enumeration probl…
A Complexity Theory for Hard Enumeration Problems
Nadia Creignou, Markus Kröll, Reinhard Pichler +2
Complexity theory provides a wealth of complexity classes for analyzing the complexity of decision and counting problems. Despite the practical relevance of enumeration problems, t…
Parameterized Enumeration with Ordering
Nadia Creignou, Raïda Ktari, Arne Meier +3
The classes Delay-FPT and Total-FPT recently have been introduced into parameterized complexity in order to capture the notion of efficiently solvable parameterized enumeration pro…
Paradigms for Parameterized Enumeration
Nadia Creignou, Arne Meier, Julian-Steffen Müller +2
The aim of the paper is to examine the computational complexity and algorithmics of enumeration, the task to output all solutions of a given problem, from the point of view of para…