基于图分解的(3,4)-CNF公式的可满足性

• 作者: 张海月 秦永彬 聂国霞
• 来源期刊: 计算机与数字工程
• 学科: 工学
• 关键词: (3,4)-CNF公式 因子图 (3,4)-双向正则二部图 可满足问题
• 年，卷（期）: 2015,（5）
• 所属期刊栏目: 算法与分析
• 页码范围: 766-770,891
• 页数: 6页
• 分类号: TP301
• 字数: 5126字
• 语种: 中文
• DOI: 10.3969/j.issn1672-9722.2015.05.004

摘要

对于规则的(3,4)-CNF公式F,公式F对应的因子图GF恰好是一个(3,4)-双向正则二部图.利用正则二部图的有关性质,证明了对于任意的(3,4)-CNF公式F,若其对应的因子图GF能够被划分为两个(3,2)-双向正则二部图,则F是可满足的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	秦永彬	贵州大学计算机科学与技术学院	63	213	8.0	10.0
2	张海月	贵州大学计算机科学与技术学院	2	4	2.0	2.0
3	聂国霞	贵州大学计算机科学与技术学院	2	6	2.0	2.0