Enumerating All Solutions of a Boolean CSP by Non-decreasing Weight
From MaRDI portal
Publication:3007678
DOI10.1007/978-3-642-21581-0_11zbMath1330.68108OpenAlexW1831347135MaRDI QIDQ3007678
Johannes Schmidt, Nadia Creignou, Frédéric Olive
Publication date: 17 June 2011
Published in: Theory and Applications of Satisfiability Testing - SAT 2011 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-21581-0_11
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Classical propositional logic (03B05)
Related Items (6)
Paradigms for parameterized enumeration ⋮ The Weight in Enumeration ⋮ Incremental delay enumeration: space and time ⋮ Parameterized Enumeration for Modification Problems ⋮ Connecting knowledge compilation classes and width parameters ⋮ Structural tractability of enumerating CSP solutions
Cites Work
- Unnamed Item
- Unnamed Item
- Planar graph coloring is not self-reducible, assuming P\(\neq NP\)
- Parameterized complexity of constraint satisfaction problems
- Efficient algorithms for the problems of enumerating cuts by non-decreasing weights
- Lower bounds for three algorithms for transversal hypergraph generation
- On generating all maximal independent sets
- On the algebraic structure of combinatorial problems
- Tractable decision for a constraint language implies tractable search
- Complexity of constraints. An overview of current research themes
- Nonuniform Boolean constraint satisfaction problems with cardinality constraint
- On the Hardness of Losing Weight
- Enumeration of the Monomials of a Polynomial and Related Complexity Classes
- Enumerating All Solutions for Constraint Satisfaction Problems
- On Acyclic Conjunctive Queries and Constant Delay Enumeration
- On generating all solutions of generalized satisfiability problems
- Algorithm Theory - SWAT 2004
- The complexity of satisfiability problems
- Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
- Partial Polymorphisms and Constraint Satisfaction Problems
- Introduction to the Maximum Solution Problem
This page was built for publication: Enumerating All Solutions of a Boolean CSP by Non-decreasing Weight
