Tata Institute of Fundamental Research
Exact Algorithms for Some Graph Coloring and Covering Problems
Master's Thesis Seminar
Speaker:
Siddharth Bhandari
Organiser:
Vinod M. Prabhakaran
Date:
Tuesday, 13 Jun 2017, 11:00 to 12:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Inclusion-Exclusion based methods will be presented for solving exactly some graph coloring and covering problems. In particular this solves the problem of finding the Chromatic number of a graph in $O^*(2^n)$ time, which was open till 2006 (Björklund and Husfeldt, FOCS 2006). Then, an alternate approach of using Fast Subset Convolution will be presented: this generalizes the Inclusion-Exclusion based methods at a cost. Finally, an algorithm for computing the b-fold Fractional Chromatic number in $O^*(2^{(n log(2b))})$ time, will be presented.
| Speaker: | Siddharth Bhandari |
| Organiser: | Vinod M. Prabhakaran |
| Date: | Tuesday, 13 Jun 2017, 11:00 to 12:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Inclusion-Exclusion based methods will be presented for solving exactly some graph coloring and covering problems. In particular this solves the problem of finding the Chromatic number of a graph in $O^*(2^n)$ time, which was open till 2006 (Björklund and Husfeldt, FOCS 2006). Then, an alternate approach of using Fast Subset Convolution will be presented: this generalizes the Inclusion-Exclusion based methods at a cost. Finally, an algorithm for computing the b-fold Fractional Chromatic number in $O^*(2^{(n log(2b))})$ time, will be presented.