ICS Theory Group

ICS 269, Winter 2002: Theory Seminar


14 Feb 2003:
Maximal Independent Sets and Their Use in Colouring Algorithms
Jesper Makholm Byskov

I will talk about maximal independent sets in graphs and why they are useful for colouring graphs. I will for all k show tight bounds on the number of maximal independent sets of size at most k, and give algorithms for finding all maximal independent sets of size at most k. Then I will show how to use these algorithms to design better algorithms for colouring graphs.

I will also discuss a generalisation of maximal independent sets, namely maximal k-colourable subgraphs and give some upper and lower bounds on the number of these.

Part of the talk is based on my SODA paper: "Algorithms for k-Colouring and Finding Maximal Independent Sets".