Tata Institute of Fundamental Research
Parameterized Algorithms for Minimum Vertex Cover Problem
Seminar
Speaker:
Bodhayan Roy
Organiser:
Ankush Agarwal
Date:
Friday, 21 Mar 2014, 14:30 to 16:00
Venue:
D-405 (D-Block Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Bodhayan Roy |
| Organiser: | Ankush Agarwal |
| Date: | Friday, 21 Mar 2014, 14:30 to 16:00 |
| Venue: | D-405 (D-Block Seminar Room) |
(Scan to add to calendar)
Abstract:
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.