基于因子图求解(3,4=)-CNF公式类下可满足问题
聂国霞1
秦永彬2
许道云2
1.贵州大学理学院 贵阳 5500252.贵州大学计算机科学与信息学院 贵阳 550025
摘要：合取范式(CNF)公式F是(3,4=)-CNF公式,如果F中每个子句的长度是3,每个变元出现的次数恰好为4次.与(3,4=)-CNF公式所关联的因子图是一类规则的二部图,即每个子句结点的度为3,每个变元结点的度为4,此类规则图被称为(3,4)-双向正则二部图.对于一个(3,4=)-CNF公式F,如果它关联的因子图GF有P7路径因子,则F可满足.
关键词：(3,4=)-CNF公式因子图(34)-双向正则二部图可满足问题
分类号：TP301(计算技术、计算机技术)
资助基金：国家自然科学基金(61262006)
论文发表日期：2013-01-01
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：4( 686-689 )
英文信息