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

Abstract:

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 th e vertex covering problem. One is the connected vertex covering problem and the other is the weighted tree covering problem. The paper gives the fixed p arameter tractable algorithm for these problems, respectively, and it is the best results for the time being.

Key words: parameter complexity, fixed-parameter tractable algorithm, vertex covering, connected vertex covering