Tata Institute of Fundamental Research
Fast Subset Convolution for Exact Exponential Algorithms
STCS Student Seminar
Speaker:
Siddharth Bhandari
Organiser:
Tulasi mohan Molli
Date:
Friday, 10 Feb 2017, 16:00 to 17:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
I will present a technique know as fast subset convolution for Exact Exponential Algorithms. We will see how this technique immediately gives algorithms for a bunch of coloring and covering problems on graphs, and in particular 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)
| Speaker: | Siddharth Bhandari |
| Organiser: | Tulasi mohan Molli |
| Date: | Friday, 10 Feb 2017, 16:00 to 17:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
I will present a technique know as fast subset convolution for Exact Exponential Algorithms. We will see how this technique immediately gives algorithms for a bunch of coloring and covering problems on graphs, and in particular 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)