Tractable constraints on ordered domains
From MaRDI portal
Publication:5917444
DOI10.1016/0004-3702(95)00107-7zbMath1013.68503OpenAlexW2016639451MaRDI QIDQ5917444
Martin C. Cooper, Peter G. Jeavons
Publication date: 4 February 2003
Published in: Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0004-3702(95)00107-7
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Disjunctions, independence, refinements ⋮ Tractability in constraint satisfaction problems: a survey ⋮ Tropically convex constraint satisfaction ⋮ Domain permutation reduction for constraint satisfaction problems ⋮ Representing and solving finite-domain constraint problems using systems of polynomials ⋮ Revisiting global constraint satisfaction ⋮ Unnamed Item ⋮ Tractability of explaining classifier decisions ⋮ A hybrid tractable class for non-binary CSPs ⋮ The power of propagation: when GAC is enough ⋮ Learnability of quantified formulas. ⋮ Hybrid Tractable Classes of Constraint Problems ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ The Broken-Triangle Property with Adjoint Values ⋮ Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms ⋮ The complexity of soft constraint satisfaction ⋮ Model-based computing: Developing flexible machine control software ⋮ On bijunctive predicates over a finite set ⋮ The expressive power of valued constraints: Hierarchies and collapses ⋮ Complexity of clausal constraints over chains ⋮ Max-Closed Semilinear Constraint Satisfaction ⋮ Soft arc consistency revisited ⋮ Approximability of clausal constraints ⋮ Tractability of quantified temporal constraints to the max ⋮ Tractable constraints in finite semilattices ⋮ Combinatorial problems raised from 2-semilattices ⋮ A new tractable class of constraint satisfaction problems ⋮ A note on some collapse results of valued constraints ⋮ Fine-grained conflict resolution in constraint satisfaction problems ⋮ A polynomial relational class of binary CSP ⋮ Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination ⋮ Parameterized Complexity of the Workflow Satisfiability Problem ⋮ Galois connections for patterns: an algebra of labelled graphs ⋮ On m-Junctive Predicates on a Finite Set ⋮ Minimization of locally defined submodular functions by optimal soft arc consistency ⋮ Constraints, consistency and closure ⋮ On weak positive predicates over a finite set ⋮ On a new extension of BTP for binary CSPs ⋮ Introduction to the Maximum Solution Problem ⋮ Feasibility checking in Horn constraint systems through a reduction based approach ⋮ An efficient algorithm for a class of constraint satisfaction problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Network-based heuristics for constraint-satisfaction problems
- From local to global consistency
- A generic arc-consistency algorithm and its specializations
- Structure identification in relational data
- Consistency in networks of relations
- Fast parallel constraint satisfaction
- Decomposing constraint satisfaction problems using database techniques
- Characterising tractable constraints
- Networks of constraints: Fundamental properties and applications to picture processing
- Constraint relaxation may be perfect
- A sufficient condition for backtrack-bounded search
- The complexity of satisfiability problems
