期刊文献+

顶点覆盖问题线性内核算法 被引量:2

Linear Kernelization Algorithm for the Vertex Cover Problem
下载PDF
导出
摘要 参数复杂性作为算法研究的一个重要分支近10年在国际上受到了广泛的关注,线性内核问题作为参数复杂性研究的一类重要问题被广泛研究.主要给出了顶点覆盖问题的线性内核算法,在国内首次从理论上证明了顶点覆盖问题存在线性内核.算法首先通过顶点覆盖问题的2近似算法,将图的顶点集合分成两个顶点集合A,B,进而通过一系列规约将原始图的顶点覆盖问题转换到新图的顶点覆盖问题,然后证明了新图的顶点数目至多为2k,并且2k是这个问题的下界(k为参数具体定义见文章). Parameterized complexity as a branch of the algorithm research gets more worldwide attention recent years. Linear kernel as the important field in research of Parameterized Complexity is widely studied by computer scientists. In this paper, a linear kernel algorithm of the vertex cover problem is given and the correctness of the algorithm is also shown and it is a first proof of linear kernel in China. The following is a brief description of the algorithm. First, a 2-approximation algorithm of the vertex cover problem is used to get two sets of vertices A and B, and then many reduction rules are used to get a new graph, and it is shown that the original graph has vertex cover of size k if and only if the new graph has vertex cover of size k′. Finally, it is proved that the total number of the vertices in the new graph is bounded by 2k, which means a linear kernel, and 2k is the lower bound of this problem.
出处 《计算机研究与发展》 EI CSCD 北大核心 2008年第z1期53-56,共4页 Journal of Computer Research and Development
基金 上海重点学科建设基金项目(B412) 国家自然科学基金项目(60496321,60703091)
关键词 参数复杂性 内核化 线性内核 定点覆盖 parameterized complexity kernelization linear kernel vertex cover
  • 相关文献

参考文献7

  • 1[1]M R Fellows,M A Langston.Nonconstructive tools for proving polynomial-time decidability.Journal of the ACM,1988,35:727-739
  • 2[2]M R Fellows,M A Langston.On search,decision and the efficiency of polynomial-time algorithms.Journal of Computer and Systems Sciences,1994,49:769-779
  • 3[3]R G Downey,M R Fellows.Parameterized Complexity.Berlin:Springer-Verlag,1999
  • 4[4]J Chen,I Kanj,W Jia.Vertex cover:Further observations and further improvements.Journal of Algorithms,2001,41:280-301
  • 5[5]T H Cormen,C E Leiserson,R L Rivest,et al.Introduction to Algorithms.Cambridge:MIT Press,2001
  • 6[6]H L Bodlaender.A cubic kernel for feedback vertex set.Utrecht University,Tech Rep:UU-CS-2006-042,2006
  • 7[7]K Burrage,V Estivill-Castro,M R Fellows,et al.The undirected feedback vertex set problem has a poly(k) kernel.In:Proc of the 2nd Int'l Workshop on Parmaterized and Exact Computation.Berlin:Springer-Verlag,2006

同被引文献10

  • 1Garey M R Johnson D S.Strong NP-completeness re- sults:motivation?examples,and implications[J].Jour- nal of ACM,1978,25(3):499-508.
  • 2Chlebik M,Chlebikova J.Crown reductions for the minimum weighted vertex cover problem[J].Discrete Applied Mathematics,2008,156(3):292-312.
  • 3Chen J N,Kanj J A.On approximating minimum vertex cover for graphs with perfect matching[J].Theoretical Computer Science,2005,337(1):305-318.
  • 4Chen J,Kani I A,Xia G.Improved upper bounds for vertex cover[J].Theoretical Computer Science,2010,411(40):3736-3756.
  • 5Xu X S,Ma J.An efficient simulated annealing algo- rithm for the minimum vertex cover problem[J].Neu- rocomputing,2006,69(7):913-916.
  • 6Shyu S J,Yin P Y,Lin B M T.An ant colony optimi- zation algorithm for the minimum weight vertex cover problem[J].Annals of Operations Research,2004,131(1):283-304.
  • 7宁爱兵,马良,熊小华.最小顶点覆盖快速降阶算法[J].小型微型计算机系统,2008,29(7):1282-1285. 被引量:9
  • 8闫兴篡,殷建平,蔡志平,刘湘辉.求图的最小顶点覆盖集的一个近似算法[J].哈尔滨工业大学学报,2008,40(7):1131-1135. 被引量:8
  • 9刘海涛,续欣莹,谢珺,谢刚.信息观下增量式属性约简方法研究[J].小型微型计算机系统,2016,37(2):375-380. 被引量:5
  • 10郑光勇,徐雨明,李肯立,孙士兵.一种混合化学反应优化算法求解最小顶点覆盖问题[J].计算机应用研究,2016,33(9):2669-2672. 被引量:1

引证文献2

二级引证文献4

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部