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

Hardness of the edge-disjoint Min-Min problem in undirected graphs

作　　者：郭龙坤[1] 沈鸿[1] 

机构地区：[1]中国科学技术大学计算机学院,合肥230026

出　　处：《中国科学院研究生院学报》2012年第4期549-554,共6页Journal of the Graduate School of the Chinese Academy of Sciences

基　　金：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-完全性的正确证明.We show incorrectness of the NP-completeness proof of Bhatia et al. for the edge-disjoint Min-Min problem in undirected graphs, by giving a counter example that is an unsatisfiable 3SAT instance but was classified satisfiable in the proof of Bhatia et al. We then give a proof of NP- completeness of the edge-disjoint Min-Min problem in undirected graphs, based on a reduction from the MAX-2SAT problem.

关 键 词：Min-Min问题 NP-完全 不相交路径对 MAX-2SAT问题 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]