论文部分内容阅读
Bhatia等指出,Xu等对无向图中的边不相交Min-Min问题的NP-完全性证明并不成立.我们首先用一个反例指出Bhatia等对Xu等的NP-完全性证明的修正依然存在错误.基于一个从MAX-2SAT的归约,我们给出了一个无向图中边不相交Min-Min问题的NP-完全性的正确证明.
无向图中边不相交Min-Min问题的复杂度
【摘 要】
：
Bhatia等指出,Xu等对无向图中的边不相交Min-Min问题的NP-完全性证明并不成立.我们首先用一个反例指出Bhatia等对Xu等的NP-完全性证明的修正依然存在错误.基于一个从MAX-2SAT
【机 构】
：
中国科学技术大学计算机学院
【出 处】
：
中国科学院研究生院学报
【发表日期】
：
2012年4期
【基金项目】
：
Supported by NSFC （622307） , the ＂ 100 Talents＂ Project of Chinese Academy of Sciences, and ChinaScholarship Council＇s State Scholarship Fund （ 2009634119 ）
其他文献
利用Riemann-zeta函数的估计及其解析方法研究了m次剩余数的一些渐近性质，得到了两个有趣的渐近公式.
教学过程是师生交往、共同发展的互动过程.教师不仅仅是知识的传授者,更是学生学习的合作者、参与者和引导者,引领学生在学习的过程中学会独立自学、交流互动,学会主动参与、
点读技术虽然发展时间不长,但在实际应用中,已被家长、学生及教师奉为小学生提升英语学习效率及兴趣的最佳工具。先进的点读技术与教学实践相结合,将对当前的小学英语教育模
我校政治教研组去年承担了泉州市教育科学规划课题＂乡土资源在思想政治课教学中的开发和利用＂的研究工作。在课题的研究过程中,我们试图创新乡土资源在思想政治课教学中的呈现
班主任工作是中小学校教育工作的重中之重。班主任工作时间长了，就会形成自己的思维定势和教育方法，这本无可厚非，但有些思维定势和教育方法是有问题的。例如，在和学生谈话时，有些
针对蠕虫仿真中大量小型对象的特点,对GTNetS的内存管理机制进行系统研究,提出小型对象内存分配技术.实验结果表明,小型对象分配技术可以有效减少系统的最大内存使用量,进而