【摘 要】
：
Motivated by a previous work showing a new NP-complete decision problem,the Multistage graph Simple Path problem (MSP) possesses a novel polynomial-time heuristic algorithm,which has undergone extensi
【机 构】
：
School of Computer Science,National University of Defence Technology,Changsha,Hunan,410073,China
【出 处】
：
2014全国理论计算机科学学术年会
论文部分内容阅读
Motivated by a previous work showing a new NP-complete decision problem,the Multistage graph Simple Path problem (MSP) possesses a novel polynomial-time heuristic algorithm,which has undergone extensive test and always give the correct answer for all instances(more than 5×107) generated up to now,we further consider the the polynomial-time solutions for several NP-complete optimization problems,including maximum satisfiability,maximum independent set,maximum clique,and maximum three-dimensional matching.In this paper,we propose polynomial reductions from the decision version of these NP-complete optimization problems to the MSP problem.Thus plus the polynomial-time heuristic algorithm for the MSP problem,we obtain the polynomial-time heuristic algorithms for these NP-complete optimization problems respectively.Although there is no broad consensus with proving the correctness of the polynomial-time heuristic algorithm for the MSP problem,the good performance of the algorithm will convince us to believe that the new obtained heuristic algorithms for these NP-complete optimization problems will most probably find the optimal solution.
其他文献
基于高感知质量的视频流的需求,如何对视频流的用户体验质量进行有效而准确的评估成为目前研究的一个热点.本文论述了基于视频流的用户体验质量的预测方法,重点阐述了几种典型的QoE预测模型.首先,对影响用户体验质量的因素进行了分析并指出存在的问题;然后,对用户体验质量的不同预测方法进行了分析和论述;最后,就网络视频流的用户体验质量预测方法的进一步发展提出了若干技术与研究展望.
语音识别作为人机语音通信的一种重要技术手段,其产品在人机交互应用中所占比例越来越大,但其程序繁琐运行时间长是影响其实用化的主要问题.开放式多媒体应用平台OMAP有非对称双核结构优势,但双核间的通讯问题是影响其性能的一项关键技术.DSPGateway作为一种双核通讯架构,具有功能强大、使用灵活等优点,但目前并未得到广泛使用.为此,本论文以DSPGateway为软件架构平台,以OMAP5912为系统硬
The application layer of Distributed Denial of Service (DDoS) has the characteristics of low rate,legitimate messages.The existing methods are mainly based on supervised learning which needs enough la
Over past decades,there has been more and more large scale sensors deployed in a wide range of application areas.Due to the innate imprecision of sensor observations,researchers devote to find an effi
With the rapid development of the Internet of Things,adaptive technology for the Internet of Things has gained a great deal of attention.Environment perception as an technology to support adaptive net
Routing algorithm with more flexibility and fewer virtual channels is essential for high performance multicomputer systems.For three-dimensional mesh-connected networks,the traditional planar-adaptive
It is well-known that model combination can improve prediction performance of regression model.We investigate the model combination of Support Vector Regression (SVR) with regularization path in this
This paper designed a kind of optimization algorithm for image registration.By combining with cultural particle swarm optimization (CPSO),a novel image registration algorithm is outlined in this paper
Profinite topology plays a key role in formal languages.Depending on the fact that Boolean algebra of regular languages is in one-to-one correspondence to clopen of profinite topological space,we prov
To further explore the up-to techniques for bisimulation in the coalgebra setting,we investigate a special kind of functor,i.e.,product functor in this paper.Specifically,when F is the product of n su