On planar valued CSPs

作者：

Highlights：

• First study of planar VCSPs.

• Necessary conditions on tractability of Boolean planar VCSPs.

• Complexity classification of conservative planar VCSPs.

摘要

•First study of planar VCSPs.•Necessary conditions on tractability of Boolean planar VCSPs.•Complexity classification of conservative planar VCSPs.

论文关键词：Constraint satisfaction,Planarity,Multimorphisms,Valued constraint satisfaction

论文评审过程：Received 14 June 2016, Revised 1 January 2017, Accepted 7 March 2017, Available online 18 March 2017, Version of Record 11 April 2017.

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