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

Fixed Parameter Tractable Algorithms for the Two Variants of the Vertex Covering Problem

作　　者：洪翔宇[1] 蔡晟[1] 

机构地区：[1]复旦大学信息工程学院计算机系,上海200433

出　　处：《计算机工程与科学》2008年第12期79-81,84,共4页Computer Engineering & Science

摘　　要：参数复杂性作为算法研究的一个重要分支,近十年来在国际上受到了广泛的关注,确定参数可解算法是参数复杂性研究的一类重要问题,因此被广泛研究。本文主要研究了顶点覆盖问题的两个变体问题:一个是连接的顶点覆盖问题,二是含权的树型顶点覆盖问题。这两个问题都是对原始的顶点覆盖问题加入了一些限制的变体问题。本文给出了这两个问题的确定参数可解算法,并且是目前的最好结果。Parameterized complexity as a branch of the algorithm research gets more worldwide attention in recent years. The fixed-parameter tractable algorithm as an important field in the research of parameterized complexity is widely studied by computer scientists. This paper mainly studies two variants of the vertex covering problem. One is the connected vertex covering problem and the other is the weighted tree covering problem. The paper gives the fixed parameter tractable algorithm for these problems, respectively, and it is the best results for the time being.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]