论文部分内容阅读
针对文献[1,2]提出的MSP问题,研究了MSP问题与着色问题、子图同构问题的对应关系,揭示了MSP问题所反映的NP完全问题的共性;分析了MSP问题的相变现象,为文献[1,2]提出的多项式时间算法框架的测试提供了难例产生方法。
MSP问题NP完全性研究
【摘 要】
：
针对文献[1,2]提出的MSP问题,研究了MSP问题与着色问题、子图同构问题的对应关系,揭示了MSP问题所反映的NP完全问题的共性;分析了MSP问题的相变现象,为文献[1,2]提出的多项式
【机 构】
：
国防科技大学计算机学院
【出 处】
：
计算机科学
【发表日期】
：
2015年7期
【基金项目】
：
国家自然科学基金（61272010）资助
其他文献
快速稀疏描述分类法(FSRC)与协同描述分类法(CRC)是在压缩感知理论的基础上发展而来的,不同的侧重点限制了两者在人脸识别上的进一步提升。针对此,提出了融合快速稀疏描述与协同描述的人脸识别方法。首先,将人脸镜像图像引入样本库;然后,利用FSRC与CRC方法求解残差矩阵;最后,利用加权信息融合的方式将两者的残差矩阵进行权值加和,依据最小值所对应的位置信息求取识别率。公共人脸数据库的实验表明,所提方
近年来,互联网上涌现出大量结构化的表格数据,网络表格的价值不仅在于数据本身,还在于数据之间的关系。只有探测出表格之间潜在的关系,方能更好地利用这些结构化数据。因此提
研究了基于单载波频分多址（SC-FDMA）的宽带认知无线电网络中非授权用户（NU）的最优功率分配（OPA）问题。首先给出了基于SC-FDMA的宽带认知无线电网络中非授权用户对授权用户的干扰功
针对山东汛期暴雨天气多,汛情紧急的情况,为能够使群众安全、高效、有序地撤离受灾区域,省防洪防汛指挥部决定在日照市仕阳水库组织应急防洪、防汛演练,即对泄洪闸附近大量的
基于Reyhani Masoleh提出的GF（2^m）高斯正规基乘法实现了三拍非流水的正规基乘法器,并基于该乘法器实现了一种高性能López-Dahab标量乘硬件结构.Reyhani-Masoleh算法利用
为了研究发泡剂和促泡剂含量对乳化炸药发泡速度和爆速的影响,对不同含量下发泡剂和促泡剂进行了密度测量和爆速实验。结果表明:在相同含量促泡剂和相同发泡时间下,乳化炸药
燃气涡轮机已被广泛运用于现代工业中,其跳闸事件的发生将产生巨大的经济损失,因此,对燃气涡轮机的跳闸事件进行预测有重要的经济意义。然而,燃气涡轮机跳闸的预测研究是一个
片上网络（Network on Chip,NoC）通过仲裁机制控制各个端口间的数据交换。经典的RR（Round-Robin）算法保障了各端口间的公平性,但却难以为时延敏感业务提供具有低数据交换等待时延
随着无线传感技术的快速发展,无线体域网在远程医疗、智能家居等方面的应用日渐成为研究热点。监狱作为一个特殊场所,对囚犯的日常行为监控是必不可少的。准确而有效的监控系统能够在囚犯有异常行为发生时及时告警,这有助于监狱的管理,并阻止危险事故的发生。在监狱环境下,提出一种基于无线体域网的囚犯异常行为识别方法,即通过一个腕带式加速度传感器获取囚犯活动时的三轴加速度数据,采用分类算法判断是否有打架斗殴等异常行
随着Web服务以及Web服务组合应用软件在分布式网络中的广泛应用,Web服务的规模和复杂性也在不断地增加,这使得服务在运行过程中可能产生各种故障,因此对服务系统进行及时的故