基于因子图求解(3,4=)-CNF公式类下可满足问题

• 作者: 秦永彬 聂国霞 许道云
• 来源期刊: 计算机与数字工程
• 学科: 工学
• 关键词: (3,4=)-CNF公式 因子图 (3,4)-双向正则二部图 可满足问题
• 年，卷（期）: 2013,（5）
• 所属期刊栏目: 算法与分析
• 页码范围: 686-689
• 页数: 4页
• 分类号: TP301
• 字数: 5703字
• 语种: 中文

摘要

合取范式(CNF)公式F是(3,4=)-CNF公式,如果F中每个子句的长度是3,每个变元出现的次数恰好为4次.与(3,4=)-CNF公式所关联的因子图是一类规则的二部图,即每个子句结点的度为3,每个变元结点的度为4,此类规则图被称为(3,4)-双向正则二部图.对于一个(3,4=)-CNF公式F,如果它关联的因子图GF有P7路径因子,则F可满足.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许道云	贵州大学计算机科学与信息学院	125	460	12.0	16.0
2	秦永彬	贵州大学计算机科学与信息学院	63	213	8.0	10.0
3	聂国霞	贵州大学理学院	2	6	2.0	2.0