| Cover problem is a class of important fundamental problem in computational geometry and combinatorial optimization. Studying cover problems makes not only great theoretical significance but also much important practical significance in computational biology, circuit design, network address selection, process flow analysis, etc. There are many cover problems, abstracted from practical applications, such as Vertex Cover, Tree Cover, Hyperplane-Cover, Set Cover, etc. In this paper, we study the Hyperplane-Cover problem and the Above Guarantee Vertex Cover problem on graphs with perfect matching.For the Hyperplane-Cover problem, a deterministic parameterized algorithm for the Line-Cover problem (a special case of Hyperplane-Cover problem) with running time O*((0.736k)k) is proposed firstly by further analyzing the structure of the problem, which significantly improves the previous best result O*((k/2.2)2k). Generally, a deterministic parameterized algorithm for the Hyperplane-Cover problem with running time O*((dk)!/((d!)kk!)) is given, which greatly improves the previous best result O*(kd(k+1)).For the Above Guarantee Vertex Cover problem on graphs with perfect matching, there exists a fixed parameterized algorithm with running time O*(15k). We present an improved algorithm, the main idea of which is as follows. Firstly, we, using iterative compression technique, transform the PM-AGV-VC problem to a special Vertex Cover problem on Konig graph with perfect matching; later, we transform the latter to a variation of the parameterized 2-ASLASAT problem (KPM-2-AASAT problem); finally, through further analyzing the structure of the problem we, using branch and search method and implicit parameter technique, provide a parameterized algorithm for the KPM-2-AASAT problem. The total complexity of our algorithm is O*(9k), improving the previous best algorithm.Finally, the study work on the problems, mentioned above, is summed up and some related future researches are proposed briefly.
|
PDF Full Text Request