Small maximal independent sets and faster exact graph coloring

David Eppstein
J. Graph Algorithms & Applications 7(2):131–140, 2003
Proc. 7th Worksh. Algorithms and Data Structures (WADS 2001), Lecture Notes in Computer Science 2125, Frank K. H. A. Dehne, Jörg-Rudiger Sack, and Roberto Tamassia, ed., Springer-Verlag, Aug 2001, pp. 462–470
ACM Computing Research Repository, cs.DS/0011009
Mathematical Reviews 2003j:05117

Cited by:

• On the number of maximal independent sets in a graph
• On the number of maximal bipartite subgraphs of a graph
• Algorithms for $k$-colouring and finding maximal independent sets
• Exact algorithms for NP-hard problems: A survey
• Colouring random graphs in expected polynomial time
• A simple and fast approach for solving problems on planar graphs
• Generating small combinatorial test suites to cover input-output relationships
• Enumerating maximal independent sets with applications to graph colouring