Constraint satisfaction with bounded treewidth revisited

作     者：Samer, Marko Szeider, Stefan 

作者机构：Univ Durham Dept Comp Sci Durham DH1 3HP England Tech Univ Darmstadt Dept Comp Sci Darmstadt Germany 

出 版 物：《JOURNAL OF COMPUTER AND SYSTEM SCIENCES》 (计算机与系统科学杂志)

年 卷 期：2010年第76卷第2期

页      面：103-114页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：EPSRC [EP/E001394/1] Funding Source: UKRI 

主　　题：Constraint satisfaction Parameterized complexity Treewidth 

摘      要：We consider the constraint satisfaction problem (CSP) parameterized by the treewidth of primal, dual, and incidence graphs, combined with several other basic parameters such as domain size and arity. We determine all combinations of the considered parameters that admit fixed-parameter tractability. (C) 2009 Elsevier Inc. All rights reserved.