Title :
Space optimal chromatic polynomial algorithm
Author :
Basenspiler, Larry ; Hain, Thomas ; King, Ben
Author_Institution :
Div. of Comput. & Inf. Sci., South Alabama Univ., Mobile, AL, USA
Abstract :
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
Keywords :
computational complexity; graph theory; chromatic polynomial algorithm; data structure; sparse graphs; vectorized algorithm; vertices; Algorithm design and analysis; Computer languages; Data structures; IEL; Mobile computing; Modems; Polynomials; Tree graphs;
Conference_Titel :
Applied Computing, 1991., [Proceedings of the 1991] Symposium on
Conference_Location :
Kansas City, MO
Print_ISBN :
0-8186-2136-2
DOI :
10.1109/SOAC.1991.143849
