顶点覆盖问题线性内核算法
参数复杂性作为算法研究的一个重要分支近10年在国际上受到了广泛的关注,线性内核问题作为参数复杂性研究的一类重要问题被广泛研究.主要给出了顶点覆盖问题的线性内核算法,在国内首次从理论上证明了顶点覆盖问题存在线性内核.算法首先通过顶点覆盖问题的2近似算法,将图的顶点集合分成两个顶点集合A,B,进而通过一系列规约将原始图的顶点覆盖问题转换到新图的顶点覆盖问题,然后证明了新图的顶点数目至多为2k,并且2k是这个问题的下界(k为参数具体定义见文章).
参数复杂性 内核化 线性内核 顶点覆盖
蔡晟 Rudolf Fleischer 朱洪
复旦大学信息工程学院计算机系,上海,200433 华东师范大学软件学院,上海,200062
国内会议
南宁
中文
53-56
2007-11-01（万方平台首次上网日期，不代表论文的发表时间）