Thore Husfeldt
News
Paper on STACS 2008
The STACS 2008 committee just accepted our submission Trimmed Moebius Inversion and Graphs of Bounded Degree. This is joint work with Andreas Björklund, Petter Kaski, and Mikko Koivisto.
In some earlier work we showed that the graph colouring problem can be solved in time 2npoly(n); which punctuated a decades-long story of incremental improvements of the base of the exponent, from the obvious-by-dynamic-programming 3 via 2.4423, 2.4151, 2.4023, and 2.3236.
Our new papers shows that the story doesn’t end with 2, as tempting as this number looks. At least not for bounded-degree graphs. Specifically, we show that every bounded-degree graph can be coloured in time cnpoly(n) for some constant c strictly less than two, depending on the degree but not on n.
The techniques involve some manipulations “inside” Yates’s algorithm for Moebius inversion, and some neat combinatorics about families of intersecting sets based on a result of Chung et al..
Fri, 14 Dec 2007 | Category: News | Permanent link