基于图分解的(3,4)-CNF公式的可满足性
张海月
秦永彬
聂国霞
1.贵州大学计算机科学与技术学院 贵阳 5500252.贵州大学计算机科学与技术学院 贵阳 5500253.贵州大学计算机科学与技术学院 贵阳 550025
摘要：对于规则的(3,4)-CNF公式F,公式F对应的因子图GF恰好是一个(3,4)-双向正则二部图.利用正则二部图的有关性质,证明了对于任意的(3,4)-CNF公式F,若其对应的因子图GF能够被划分为两个(3,2)-双向正则二部图,则F是可满足的.
关键词：(3,4)-CNF公式因子图(34)-双向正则二部图可满足问题
分类号：TP301(计算技术、计算机技术)
资助基金：国家自然科学基金(61262006)
论文发表日期：2015-01-01
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：6( 766-770,891 )
英文信息