School of Technology and Computer Science Seminars
Exact Algorithms for Some Graph Coloring and Covering Problems
by Siddharth Bhandari (School of Technology and Computer Science, TIFR)
Tuesday, June 13, 2017
from
to
(Asia/Kolkata)
at A-201 (STCS Seminar Room)
at A-201 (STCS Seminar Room)
Description |
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. |