Classifying the complexity of constraints using finite algebras

Classifying the complexity of constraints using finite algebras

他のバージョン（1件）を表示する

Many natural combinatorial problems can be expressed as constraint satisfaction problems. This class of problems is known to be NP-complete in general, but certain restrictions on the form of the constraints can ensure tractability. Here we show that any set of relations used to specify the allowed...

書誌詳細
主要な著者:	Bulatov, A, Jeavons, P, Krokhin, A
フォーマット:	Journal article
言語:	English
出版事項:	2005

類似資料

Classifying the complexity of constraints using finite algebras
著者:: Bulatov, A, 等
出版事項: (2005)

Constraint satisfaction problems and finite algebras
著者:: Bulatov, A, 等
出版事項: (2000)

Constraint satisfaction problems and finite algebras
著者:: Bulatov, A, 等
出版事項: (2000)

The Complexity of Constraint Satisfaction: An Algebraic Approach
著者:: Krokhin, A, 等
出版事項: (2004)

The complexity of maximal constraint languages
著者:: Bulatov, A, 等
出版事項: (2001)

The complexity of maximal constraint languages
著者:: Bulatov, A, 等
出版事項: (2001)

Quantified constraints: Algorithms and complexity
著者:: Borner, F, 等
出版事項: (2003)

Quantified constraints: algorithms and complexity
著者:: Börner, F, 等
出版事項: (2003)

Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey
著者:: Krokhin, A, 等
出版事項: (2003)

Functions of multiple−valued logic and the complexity of constraint satisfaction: A short survey
著者:: Krokhin, A, 等
出版事項: (2003)

Structural Theory of Automata‚ Semigroups‚ and Universal Algebra
著者:: Krokhin, A, 等
出版事項: (2003)

An algebraic approach to multi-sorted constraints
著者:: Bulatov, A, 等
出版事項: (2003)

An algebraic approach to multi−sorted constraints
著者:: Bulatov, A, 等
出版事項: (2003)

The complexity of constraint satisfaction games and QCSP
著者:: Boerner, F, 等
出版事項: (2009)

The complexity of constraint satisfaction games and QCSP
著者:: Börner, F, 等
出版事項: (2009)

Finite semigroups imposing tractable constraints
著者:: Bulatov, A, 等
出版事項: (2002)

Soft constraints: Complexity and multimorphisms
著者:: Cohen, D, 等
出版事項: (2003)

The complexity of soft constraint satisfaction
著者:: Cohen, D, 等
出版事項: (2006)

The complexity of soft constraint satisfaction
著者:: Cohen, D, 等
出版事項: (2006)

Soft constraints: complexity and multimorphsims
著者:: Cohen, D, 等
出版事項: (2003)

An algebraic characterisation of complexity for valued constraints
著者:: Cohen, D, 等
出版事項: (2006)

An algebraic characterisation of complexity for valued constraints
著者:: Cohen, D, 等
出版事項: (2006)

A complete classification of complexity in Allen's algebra in the presence of a non−trivial basic relation
著者:: Krokhin, A, 等
出版事項: (2001)

Algebraic structures in combinatorial problems
著者:: Bulatov, A, 等
出版事項: (2001)

Constraint satisfaction problems on intervals and lengths
著者:: Krokhin, A, 等
出版事項: (2004)

Constraint satisfaction problems on intervals and lengths
著者:: Krokhin, A, 等
出版事項: (2004)

Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra
著者:: Krokhin, A, 等
出版事項: (2003)

Reasoning about temporal relations : the tractable subalgebras of Allen's interval algebra
著者:: Krokhin, A, 等
出版事項: (2003)

Constraints and Universal Algebra
著者:: P.G.Jeavons, 等
出版事項: (1998)

An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection.
著者:: Cohen, D, 等
出版事項: (2011)

An algebraic theory of complexity for valued constraints: Establishing a Galois connection
著者:: Cohen, D, 等
出版事項: (2010)

An algebraic theory of complexity for valued constraints: Establishing a Galois connection
著者:: Cohen, D, 等
出版事項: (2011)

An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection
著者:: Cohen, D, 等
出版事項: (2010)

An algebraic theory of complexity for valued constraints: Establishing a Galois connection
著者:: Cohen, D, 等
出版事項: (2011)

Tractable constraints closed under a binary operation
著者:: Bulatov, A, 等
出版事項: (2000)

A maximal tractable class of soft constraints
著者:: Cohen, D, 等
出版事項: (2004)

A maximal tractable class of soft constraints
著者:: Cohen, D, 等
出版事項: (2004)

The constraint satisfaction problem: complexity and approximability
著者:: Krokhin, A, 等
出版事項: (2017)

Binarisation for valued constraint satisfaction problems
著者:: Cohen, D, 等
出版事項: (2017)

The complexity of constraint languages
著者:: Cohen, D, 等
出版事項: (2006)