Constraint satisfaction with bounded treewidth revisited

作者：

Highlights：

•

摘要

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.

论文关键词：Constraint satisfaction,Parameterized complexity,Treewidth

论文评审过程：Received 6 November 2007, Revised 26 October 2008, Available online 15 April 2009.

论文官网地址：https://doi.org/10.1016/j.jcss.2009.04.003