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

• 作者: 洪翔宇 蔡晟
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 参数复杂性 确定参数可解算法 顶点覆盖 连接顶点覆盖
• 年，卷（期）: 2008,（12）
• 所属期刊栏目: 算法研究
• 页码范围: 79-81,84
• 页数: 4页
• 分类号: TP301.6
• 字数: 4257字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2008.12.021

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	洪翔宇	复旦大学信息工程学院计算机系	1	0	0.0	0.0
2	蔡晟	复旦大学信息工程学院计算机系	3	12	2.0	3.0