Small Maximal Independent Sets and Faster Exact Graph Coloring

Details Small Maximal Independent Sets and Faster Exact Graph Coloring Small Maximal Independent Sets and Faster Exact Graph Coloring

2000-11-06

arxiv.org/abs/cs/0011009v1

J. Graph Algorithms & Applications 7(2):131-140, 2003

Computer Science

Data Structures and Algorithms

8 pages

Scientific paper

We show that, for any n-vertex graph G and integer parameter k, there are at most 3^{4k-n}4^{n-3k} maximal independent sets I \subset G with |I| <= k, and that all such sets can be listed in time O(3^{4k-n} 4^{n-3k}). These bounds are tight when n/4 <= k <= n/3. As a consequence, we show how to compute the exact chromatic number of a graph in time O((4/3 + 3^{4/3}/4)^n) ~= 2.4150^n, improving a previous O((1+3^{1/3})^n) ~= 2.4422^n algorithm of Lawler (1976).

Affiliated with

Also associated with

No associations

Rating

Small Maximal Independent Sets and Faster Exact Graph Coloring does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Small Maximal Independent Sets and Faster Exact Graph Coloring, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Small Maximal Independent Sets and Faster Exact Graph Coloring will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-707869