Space optimal chromatic polynomial algorithm
Larry Basenspiler, Thomas F. Hain, B. King · 2002
The paper describes an algorithm for calculating the chromatic polynomial of a graph. Along with some algorithmic and programming improvements, the data structure used makes the space requirement virtually optimal-linear in the size of input and independent of the density of the graph. A program based on the best previously existing algorithm was able to handle sparse graphs on up to 15 vertices. The vectorized algorithm enabled such graphs to be processed on up to 27 vertices.>