期刊导航
期刊开放获取
vip
退出
期刊文献
+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
检索
高级检索
期刊导航
共找到
2
篇文章
<
1
>
每页显示
20
50
100
已选择
0
条
导出题录
引用分析
参考文献
引证文献
统计分析
检索结果
已选文献
显示方式：
文摘
详细
列表
相关度排序
被引量排序
时效性排序
最坏情况下Min-2SAT问题的上界
被引量：
1
1
作者
谷文祥
姜蕴晖
+1 位作者
周俊萍
殷明浩
《智能系统学报》
北大核心
2012年第3期241-245,共5页
最坏情况下MaxSAT问题上界的研究已成为一个热门的研究领域.与MaxSAT问题相对的是MinSAT问题,在求解某些组合优化问题时,将其转化为MinSAT问题比转化为MaxSAT问题有着更快的速度,因此对MinSAT问题进行研究.针对Min-2SAT问题提出算法MinS...
最坏情况下MaxSAT问题上界的研究已成为一个热门的研究领域.与MaxSAT问题相对的是MinSAT问题,在求解某些组合优化问题时,将其转化为MinSAT问题比转化为MaxSAT问题有着更快的速度,因此对MinSAT问题进行研究.针对Min-2SAT问题提出算法MinSATAlg,该算法首先利用化简算法Simplify对公式进行化简,然后通过分支树的方法对不同情况的子句进行分支.从子句数目的角度分析算法的时间复杂度并证明Min-2SAT问题可在O(1.134 3m)时间内求解,对于每个变量至多出现在3个2-子句中的情况,得到最坏情况下的上界为O(1.122 5n),其中n为变量的数目.
展开更多
关键词
Max
sat
Min
sat
min-2sat
Max
sat
问题的上界
min-2sat
问题的上界
子句数目
分支树
在线阅读
下载PDF
职称材料
无向图中边不相交Min-Min问题的复杂度(英文)
2
作者
郭龙坤
沈鸿
《中国科学院研究生院学报》
CAS
CSCD
北大核心
2012年第4期549-554,共6页
Bhatia等指出,Xu等对无向图中的边不相交Min-Min问题的NP-完全性证明并不成立.我们首先用一个反例指出Bhatia等对Xu等的NP-完全性证明的修正依然存在错误.基于一个从MAX-2SAT的归约,我们给出了一个无向图中边不相交Min-Min问题的NP-完...
Bhatia等指出,Xu等对无向图中的边不相交Min-Min问题的NP-完全性证明并不成立.我们首先用一个反例指出Bhatia等对Xu等的NP-完全性证明的修正依然存在错误.基于一个从MAX-2SAT的归约,我们给出了一个无向图中边不相交Min-Min问题的NP-完全性的正确证明.
展开更多
关键词
min-
Min问题
NP-完全
不相交路径对
MAX-
2
sat
问题
原文传递
题名
最坏情况下Min-2SAT问题的上界
被引量：
1
1
作者
谷文祥
姜蕴晖
周俊萍
殷明浩
机构
东北师范大学计算机科学与信息技术学院
长春建筑学院基础教学部
出处
《智能系统学报》
北大核心
2012年第3期241-245,共5页
基金
国家自然科学基金资助项目(61070084)
国家自然科学青年基金资助项目(60803102)
中央高校基本科研业务费专项资金资助项目(11QNJJ006)
文摘
最坏情况下MaxSAT问题上界的研究已成为一个热门的研究领域.与MaxSAT问题相对的是MinSAT问题,在求解某些组合优化问题时,将其转化为MinSAT问题比转化为MaxSAT问题有着更快的速度,因此对MinSAT问题进行研究.针对Min-2SAT问题提出算法MinSATAlg,该算法首先利用化简算法Simplify对公式进行化简,然后通过分支树的方法对不同情况的子句进行分支.从子句数目的角度分析算法的时间复杂度并证明Min-2SAT问题可在O(1.134 3m)时间内求解,对于每个变量至多出现在3个2-子句中的情况,得到最坏情况下的上界为O(1.122 5n),其中n为变量的数目.
关键词
Max
sat
Min
sat
min-2sat
Max
sat
问题的上界
min-2sat
问题的上界
子句数目
分支树
Keywords
maximum
sat
isfiability
minimum
sat
isfiability
minimum two-
sat
isfiability
upper bounds for maximum
sat
isfiability
upper bounds for minimum two-
sat
isfiability
number of clauses
branching tree
分类号
TP18 [自动化与计算机技术—控制理论与控制工程]
在线阅读
下载PDF
职称材料
题名
无向图中边不相交Min-Min问题的复杂度(英文)
2
作者
郭龙坤
沈鸿
机构
中国科学技术大学计算机学院
出处
《中国科学院研究生院学报》
CAS
CSCD
北大核心
2012年第4期549-554,共6页
基金
Supported by NSFC(622307)
the"100 Talents"Project of Chinese Academy of Sciences
China Scholarship Council's State Scholarship Fund(2009634119)
文摘
Bhatia等指出,Xu等对无向图中的边不相交Min-Min问题的NP-完全性证明并不成立.我们首先用一个反例指出Bhatia等对Xu等的NP-完全性证明的修正依然存在错误.基于一个从MAX-2SAT的归约,我们给出了一个无向图中边不相交Min-Min问题的NP-完全性的正确证明.
关键词
min-
Min问题
NP-完全
不相交路径对
MAX-
2
sat
问题
Keywords
min-
Min problem
NP-completeness
disjoint path pair
MAX-
2
sat
分类号
TP301.5 [自动化与计算机技术—计算机系统结构]
原文传递
题名
作者
出处
发文年
被引量
操作
1
最坏情况下Min-2SAT问题的上界
谷文祥
姜蕴晖
周俊萍
殷明浩
《智能系统学报》
北大核心
2012
1
在线阅读
下载PDF
职称材料
2
无向图中边不相交Min-Min问题的复杂度(英文)
郭龙坤
沈鸿
《中国科学院研究生院学报》
CAS
CSCD
北大核心
2012
0
原文传递
已选择
0
条
导出题录
引用分析
参考文献
引证文献
统计分析
检索结果
已选文献
上一页
1
下一页
到第
页
确定
用户登录
登录
IP登录
使用帮助
返回顶部
