最坏情况下Min-2SAT问题的上界

• 作者: 周俊萍 姜蕴晖 殷明浩 谷文祥
• 来源期刊: 智能系统学报
• 学科: 工学
• 关键词: MaxSAT MinSAT Min-2SAT MaxSAT问题的上界 Min-2SAT问题的上界 子句数目 分支树
• 年，卷（期）: 2012,（3）
• 页码范围: 241-245
• 分类号: TP301
• 字数: 5085字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-4785.201109003

摘要

最坏情况下MaxSAT问题上界的研究已成为一个热门的研究领域.与MaxSAT问题相对的是MinSAT问题,在求解某些组合优化问题时,将其转化为MinSAT问题比转化为MaxSAT问题有着更快的速度,因此对MinSAT问题进行研究.针对Min-2SAT问题提出算法MinSATAlg,该算法首先利用化简算法Simplify对公式进行化简,然后通过分支树的方法对不同情况的子句进行分支.从子句数目的角度分析算法的时间复杂度并证明Min-2SAT问题可在O(1.134 3m)时间内求解,对于每个变量至多出现在3个2-子句中的情况,得到最坏情况下的上界为O(1.122 5n),其中n为变量的数目.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周俊萍	东北师范大学计算机科学与信息技术学院	10	82	4.0	9.0
2	谷文祥	东北师范大学计算机科学与信息技术学院	71	538	11.0	20.0
4	殷明浩	东北师范大学计算机科学与信息技术学院	35	304	10.0	16.0
7	姜蕴晖	东北师范大学计算机科学与信息技术学院	3	2	1.0	1.0