Special Issue on Selected Papers from the Seventh International Workshop on Algorithms and Data Structures, WADS 2001
Small Maximal Independent Sets and Faster Exact Graph Coloring
Vol. 7, no. 2, pp. 131-140, 2003. Regular paper.
Abstract We show that, for any n-vertex graph G and integer parameter k, there are at most 34kn 4n−3k maximal independent sets IG with |I| ≤ k, and that all such sets can be listed in time O(34kn 4n−3k). These bounds are tight when n/4 ≤ kn/3. As a consequence, we show how to compute the exact chromatic number of a graph in time O((4/3 + 34/3/4)n) ≈ 2.4150n, improving a previous O((1+31/3)n) ≈ 2.4422n algorithm of Lawler (1976).
Submitted: October 2001.
Revised: April 2002.
Communicated by Giuseppe Liotta and Ioannis G. Tollis
article (PDF)