On generating all solutions of generalized satisfiability problems
From MaRDI portal
Publication:4389761
DOI10.1051/ita/1997310604991zbMath0901.68075OpenAlexW157911545MaRDI QIDQ4389761
Nadia Creignou, Jean-Jacques Hébrard
Publication date: 24 May 1998
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/92575
Related Items
Tractability in constraint satisfaction problems: a survey, The complexity of minimal satisfiability problems, Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis, Paradigms for parameterized enumeration, On unique graph 3-colorability and parsimonious reductions in the plane, The Complexity of Boolean Surjective General-Valued CSPs, The complexity of surjective homomorphism problems-a survey, Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs, Optimal satisfiability for propositional calculi and constraint satisfaction problems., Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem, An algebraic hardness criterion for surjective constraint satisfaction., On rainbow-free colourings of uniform hypergraphs, Enumerating All Solutions of a Boolean CSP by Non-decreasing Weight, Enumerating models of DNF faster: breaking the dependency on the formula size, Gap theorems for robust satisfiability: Boolean CSPs and beyond, The Weight in Enumeration, Incremental delay enumeration: space and time, A complexity theory for hard enumeration problems, Unnamed Item, Parameterized Enumeration for Modification Problems, Efficiently enumerating hitting sets of hypergraphs arising in data profiling, Unnamed Item, Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?, Partial Polymorphisms and Constraint Satisfaction Problems, Structural tractability of enumerating CSP solutions, A Dichotomy Theorem for the Inverse Satisfiability Problem
Cites Work
- Unnamed Item
- On the complexity of H-coloring
- On generating all maximal independent sets
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Complexity of generalized satisfiability counting problems
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- The Complexity of Enumeration and Reliability Problems
- On the Structure of Polynomial Time Reducibility
- The complexity of satisfiability problems
- The complexity of theorem-proving procedures
- On sentences which are true of direct unions of algebras
