Enumerating all solutions of a Boolean CSP by non-decreasing weight

DOI10.1007/978-3-642-21581-0_11MaRDI QIDQ3007678zbMATH OpenOpenAlexFDO

Authors Nadia Creignou, Frédéric Olive, Johannes Schmidt

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

zbMATH Keywords

complexityCSPenumerationgeneralized satisfiabilitypolynomial delay

Mathematics Subject Classification ID

Classical propositional logic (03B05) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• The weight in enumeration
• Paradigms for parameterized enumeration
• Parameterized complexity of weighted satisfiability problems: decision, enumeration, counting
• The complexity of weighted Boolean \#CSP with mixed signs
• Enumerating All Solutions for Constraint Satisfaction Problems

Cites work

• Algorithm Theory - SWAT 2004
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• Complexity of constraints. An overview of current research themes
• Efficient algorithms for the problems of enumerating cuts by non-decreasing weights
• Enumerating All Solutions for Constraint Satisfaction Problems
• Enumeration of the monomials of a polynomial and related complexity classes
• scientific article; zbMATH DE number 1284420 (Why is no real title available?)
• scientific article; zbMATH DE number 1559517 (Why is no real title available?)
• Introduction to the Maximum Solution Problem
• Lower bounds for three algorithms for transversal hypergraph generation
• Nonuniform Boolean constraint satisfaction problems with cardinality constraint
• On Acyclic Conjunctive Queries and Constant Delay Enumeration
• On generating all maximal independent sets
• On generating all solutions of generalized satisfiability problems
• On the algebraic structure of combinatorial problems
• On the Hardness of Losing Weight
• Parameterized complexity of constraint satisfaction problems
• Partial Polymorphisms and Constraint Satisfaction Problems
• Planar graph coloring is not self-reducible, assuming P\(\neq NP\)
• The complexity of satisfiability problems
• Tractable decision for a constraint language implies tractable search

Cited in

(9)

• Enumerating models of DNF faster: breaking the dependency on the formula size
• Incremental delay enumeration: space and time
• Structural tractability of enumerating CSP solutions
• Paradigms for parameterized enumeration
• Parameterized enumeration for modification problems
• The weight in enumeration
• A characterization of efficiently compilable constraint languages
• On the enumeration of signatures of XOR-CNF's
• Connecting knowledge compilation classes and width parameters

This page was built for publication: Enumerating all solutions of a Boolean CSP by non-decreasing weight

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3007678)