顶点覆盖变体问题的确定参数可解算法研究

摘要：

参数复杂性作为算法研究的一个重要分支,近十年来在国际上受到了广泛的关注,确定参数可解算法是参数复杂性研究的一类重要问题,因此被广泛研究.本文主要研究了顶点覆盖问题的两个变体问题:一个是连接的顶点覆盖问题,二是含权的树型顶点覆盖问题。这两个问题都是对原始的顶点覆盖问题加入了一些限制的变体问题。本文给出了这两个问题的确定参数可解算法,并且是目前的最好结果.

关键词： 参数复杂性 确定参数可解算法 顶点覆盖 连接顶点覆盖

作者: 洪翔宇 蔡晟

作者单位: 复旦大学信息工程学院计算机系,上海,200433

会议类型: 国内会议

会议名称: 2008年全国理论计算机科学学术年会

会议地点: 西安

会议语种:中文

页码: 79-81,84

在线出版日期: 2008-09-19（万方平台首次上网日期，不代表论文的发表时间）