Fixed Parameter Tractable Algorithms for the Two Variants of the Vertex Covering Problem
Sheng Cai · Computer Engineering and Science · 2008
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.