无向图中边不相交Min-Min问题的复杂度

• 作者: 沈鸿 郭龙坤
• 来源期刊: 中国科学院研究生院学报
• 学科: 工学
• 关键词: Min-Min问题 NP-完全 不相交路径对 MAX-2SAT问题
• 年，卷（期）: 2012,（4）
• 所属期刊栏目: 计算机科学
• 页码范围: 549-554
• 分类号: TP301.5
• 字数: 1379字
• 语种: 中文

摘要

Bhatia等指出,Xu等对无向图中的边不相交Min-Min问题的NP-完全性证明并不成立.我们首先用一个反例指出Bhatia等对Xu等的NP-完全性证明的修正依然存在错误.基于一个从MAX-2SAT的归约,我们给出了一个无向图中边不相交Min-Min问题的NP-完全性的正确证明.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	沈鸿	中国科学技术大学计算机学院	8	69	4.0	8.0
2	郭龙坤	中国科学技术大学计算机学院	2	1	1.0	1.0