The Use Of Fpt-algorithm The Cbvc Problems

FPT-Algorithms (Fixed-Parameter-Tractable Algorithms) is considered a popular efficient algorithms which is used to solve several NP-complete problems. Many FPT algorithms work in two stages: Firstly, the instance is transformed into an eqrivalent one that is smaller in size. To be specific, its size is bounded by a function that depends on the parameter only. This stage is called reduction to problem kernel. Secondly, the new small instance is solved recursively by solving several derived instances with smaller, the recursion eventually terminates (either by finding a solution or by realizing that no solution exists because of k≤0). That stage is called bounded search tree.Vertex Cover Problem is a recognized NP hard problem, but it has promising extensive applications, especially, it has a rather mature application in the processing of repairing VLSI (Very Large-Scale Integration) chips for CBVC problem. With the increasing of the density of chips, more precise and rapid algorithms of Vertex Cover problem are needed, so the algorithms which combine FPT-Algorithms with CBVC problem can satisfy the demands .From a instance which algorithms is that classical results in matching theory and developed techniques of parameterized computation are nicely combined and gain itsrunning time bounded by 0(1.26k + kn), we can see the validity of the parameterizetheory and therefore draw a conclusion that FPT-Algorithms are very good , but it is not everything, only fully combine FPT-Algorithms with practice can it make out better results, the deeper it can be understand, the better we can get the results. Morever, analysing the instance, we hope more people would notice its good trait, and more people put parameterized complexity theory into use in more fields.