School of Technology and Computer Science Seminars

Parameterized Algorithms for Minimum Vertex Cover Problem

by Mr. Bodhayan Roy (School of Technology and Computer Science, TIFR)

Friday, March 21, 2014 from to (Asia/Kolkata)
at Colaba Campus ( D-405 (D-Block Seminar Room) )
Description
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.