New tractable classes from old

New tractable classes from old

Show other versions (1)

The constraint satisfaction problem is known to be NP-hard in general, but a number of restrictions of the problem have been identified over the years which ensure tractability. This paper introduces two simple methods of combining two or more tractable classes over disjoint domains, in order to syn...

Disgrifiad llawn

Manylion Llyfryddiaeth
Prif Awduron:	Cohen, D, Jeavons, P, Gault, R
Fformat:	Journal article
Iaith:	English
Cyhoeddwyd:	2003

Eitemau Tebyg

New Tractable Classes From Old
gan: Cohen, D, et al.
Cyhoeddwyd: (2003)

Implementing a test for tractability
gan: Gault, R, et al.
Cyhoeddwyd: (2004)

Implementing a test for tractability
gan: Gault, R, et al.
Cyhoeddwyd: (2004)

A maximal tractable class of soft constraints
gan: Cohen, D, et al.
Cyhoeddwyd: (2004)

A maximal tractable class of soft constraints
gan: Cohen, D, et al.
Cyhoeddwyd: (2004)

Tractable classes of binary CSPs defined by excluded topological minors
gan: Cohen, D, et al.
Cyhoeddwyd: (2015)

The order encoding: From tractable CSP to tractable SAT
gan: Petke, J, et al.
Cyhoeddwyd: (2011)

The order encoding: from tractable CSP to tractable SAT
gan: Petke, J, et al.
Cyhoeddwyd: (2011)

A Test for Tractability
gan: P.G.Jeavons, et al.
Cyhoeddwyd: (1996)

Tractable Disjunctive Constraints
gan: D.A.Cohen, et al.
Cyhoeddwyd: (1997)

The order encoding: from tractable CSP to tractable SAT (extended abstract)
gan: Petke, J, et al.
Cyhoeddwyd: (2011)

Characterising Tractable Constraints
gan: M.C.Cooper, et al.
Cyhoeddwyd: (1994)

Tractable Combinations of Global Constraints
gan: Cohen, D, et al.
Cyhoeddwyd: (2013)

Tractable combinations of global constraints
gan: Cohen, D, et al.
Cyhoeddwyd: (2013)

Building tractable disjunctive constraints
gan: Cohen, D, et al.
Cyhoeddwyd: (2000)

Building tractable disjunctive constraints
gan: Cohen, D, et al.
Cyhoeddwyd: (2000)

A Unifying Framework for Tractable Constraints
gan: P.G.Jeavons, et al.
Cyhoeddwyd: (1995)

Tractable Valued Constraints
gan: Jeavons, P, et al.
Cyhoeddwyd: (2013)

Tractable valued constraints
gan: Jeavons, P, et al.
Cyhoeddwyd: (2012)

Perfect Constraints Are Tractable
gan: Salamon, A, et al.
Cyhoeddwyd: (2008)

Perfect Constraints Are Tractable
gan: Salamon, A, et al.
Cyhoeddwyd: (2008)

A unified theory of structural tractability for constraint satisfaction problems
gan: Cohen, D, et al.
Cyhoeddwyd: (2008)

A unified theory of structural tractability for constraint satisfaction problems
gan: Cohen, D, et al.
Cyhoeddwyd: (2008)

Tractable Benchmarks For Constraint Programming
gan: Petke, J, et al.
Cyhoeddwyd: (2009)

Tractable Constraints on Ordered Domains
gan: P.G.Jeavons, et al.
Cyhoeddwyd: (1995)

A new hybrid tractable class of soft constraint problems
gan: Cooper, M, et al.
Cyhoeddwyd: (2010)

Generalising submodularity and horn clauses: Tractable optimization problems defined by tournament pair multimorphismsa
gan: Cohen, D, et al.
Cyhoeddwyd: (2008)

Generalising Submodularity and Horn Clauses: Tractable optimization problems defined by tournament pair multimorphisms
gan: Jeavons, P, et al.
Cyhoeddwyd: (2006)

Generalising submodularity and Horn clauses: tractable optimization problems defined by tournament pair multimorphisms
gan: Cohen, D, et al.
Cyhoeddwyd: (2008)

Finite semigroups imposing tractable constraints
gan: Bulatov, A, et al.
Cyhoeddwyd: (2002)

Tractable constraints closed under a binary operation
gan: Bulatov, A, et al.
Cyhoeddwyd: (2000)

A Survey of Tractable Constraint Satisfaction Problems
gan: J.K.Pearson, et al.
Cyhoeddwyd: (1997)

Hybrid tractable CSPs which generalize tree structure
gan: Cooper, M, et al.
Cyhoeddwyd: (2008)

The tractable "quadratic" class of growth and interest rate processes
gan: Gabaix, Xavier
Cyhoeddwyd: (2011)

Generalizing constraint satisfaction on trees: Hybrid tractability and variable elimination
gan: Cooper, M, et al.
Cyhoeddwyd: (2010)

Generalizing constraint satisfaction on trees: Hybrid tractability and variable elimination
gan: Cooper, M, et al.
Cyhoeddwyd: (2010)

Generalizing constraint satisfaction on trees: Hybrid tractability and variable elimination
gan: Cooper, M, et al.
Cyhoeddwyd: (2010)

Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra
gan: Krokhin, A, et al.
Cyhoeddwyd: (2003)

Reasoning about temporal relations : the tractable subalgebras of Allen's interval algebra
gan: Krokhin, A, et al.
Cyhoeddwyd: (2003)

A Tractable and Expressive Class of Marginal Contribution Nets and Its Applications
gan: Elkind, E, et al.
Cyhoeddwyd: (2009)