Parameterized Algorithms for Minimum Vertex Cover Problem



Friday, 21 March 2014, 14:30 to 16:00


  • D-405 (D-Block Seminar Room)


Abstract: An optimization problem is said to be fixed parameter tractable if there is some parameter k independent of the input size n, such that the problem can be solved in O(f(k).n^c) time, where c is a constant, and f is an arbitrary function depending only on k. So, for instances of NP-Hard problems where k is considerably small despite large sizes of n, such parameterized algorithms run in practically affordable time. In this talk we will go through some parameterized algorithms for the minimum vertex cover problem of simple graphs.