Building tractable disjunctive constraints

DOI10.1145/355483.355485MaRDI QIDQ2946994zbMATH OpenOpenAlexWikidataFDO

Authors Peter Jonsson, David A. Cohen, P. Jeavons, Manolis Koubarakis

Publication date 19 September 2015

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/355483.355485

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2080305
• New tractable classes from old
• Disjunctions, independence, refinements
• scientific article; zbMATH DE number 1008453
• Characterising tractable constraints

Cited in

(26)

• New tractable classes from old
• Solving multi-granularity temporal constraint networks
• Disjunctions, independence, refinements
• Constants and finite unary relations in qualitative constraint reasoning
• Domain permutation reduction for constraint satisfaction problems
• Complexity of clausal constraints over chains
• Tractability in constraint satisfaction problems: a survey
• Complexity and approximability of quantified and stochastic constraint satisfaction problems
• Characterizations of stable model semantics for logic programs with arbitrary constraint atoms
• Satisfying constraint sets through convex envelopes
• Modeling Disjunctive Constraints with a Logarithmic Number of Binary Variables and Constraints
• On the Computational Complexity of Monotone Constraint Satisfaction Problems
• Adding clauses to poor man's logic (without increasing the complexity)
• scientific article; zbMATH DE number 1008453 (Why is no real title available?)
• scientific article; zbMATH DE number 2080302 (Why is no real title available?)
• scientific article; zbMATH DE number 2080305 (Why is no real title available?)
• scientific article; zbMATH DE number 1755608 (Why is no real title available?)
• Improving IntSat by expressing disjunctions of bounds as linear constraints
• Parameterized complexity of the workflow satisfiability problem
• An initial study of time complexity in infinite-domain constraint satisfaction
• Constraint Satisfaction Problems with Infinite Templates
• Recent Advances in Constraints
• Almost consistent systems of linear equations
• Point algebras for temporal reasoning: Algorithms and complexity
• The complexity of equality constraint languages
• Approximability of clausal constraints

This page was built for publication: Building tractable disjunctive constraints

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