Complexity Analysis of Some Known Graph Coloring Instances
Graph coloring is an important problem in computer
science and many algorithms are known for obtaining reasonably
good solutions in polynomial time. One method of comparing
different algorithms is to test them on a set of standard graphs where
the optimal solution is already known. This investigation analyzes a
set of 50 well known graph coloring instances according to a set of
complexity measures. These instances come from a variety of
sources some representing actual applications of graph coloring
(register allocation) and others (mycieleski and leighton graphs) that
are theoretically designed to be difficult to solve. The size of the
graphs ranged from ranged from a low of 11 variables to a high of
864 variables. The method used to solve the coloring problem was
the square of the adjacency (i.e., correlation) matrix. The results
show that the most difficult graphs to solve were the leighton and the
queen graphs. Complexity measures such as density, mobility,
deviation from uniform color class size and number of block
diagonal zeros are calculated for each graph. The results showed that
the most difficult problems have low mobility (in the range of .2-.5)
and relatively little deviation from uniform color class size.
[1] C.H. Papadimitrou and K. Steiglitz, "Combinatorial Optimization:
Algorithms and Complexity", Dover, ISBN 0-486-40258-4, pp. 344.
[2] Duffany, J.L., "Statistical Characterization of NP-Complete Problems",
Foundations of Computer Science Conference, World Computer
Congress, Las Vegas, Nevada, July 14-17, 2008.
[3] Duffany, J.L. "Systems of Inequations", 4th LACCEI Conference,
Mayaguez, PR, June 21-23, 2006.
[4] Duffany, J.L. "Generalized Decision Function and Gradient Search
Technique for NP-Complete Problems", XXXII CLEI Conference,
Santiago Chile, August 20-23, 2006.
[5] Duffany, J.L., "Optimal Solution of Constraint Satisfaction Problems",
International Conference on Applied Computer Science, Sharm el Sheik,
Egypt, January, 2009.
[6] Duffany, J.L., "Equivalence Class Subset Algorithm", International
Conference Computer Information Technology, Tokyo, Japan, May,
2009.
[7] http://mat.gsia.cmu.edu/COLOR/instances.html
[8] http://www.r-project.org
[1] C.H. Papadimitrou and K. Steiglitz, "Combinatorial Optimization:
Algorithms and Complexity", Dover, ISBN 0-486-40258-4, pp. 344.
[2] Duffany, J.L., "Statistical Characterization of NP-Complete Problems",
Foundations of Computer Science Conference, World Computer
Congress, Las Vegas, Nevada, July 14-17, 2008.
[3] Duffany, J.L. "Systems of Inequations", 4th LACCEI Conference,
Mayaguez, PR, June 21-23, 2006.
[4] Duffany, J.L. "Generalized Decision Function and Gradient Search
Technique for NP-Complete Problems", XXXII CLEI Conference,
Santiago Chile, August 20-23, 2006.
[5] Duffany, J.L., "Optimal Solution of Constraint Satisfaction Problems",
International Conference on Applied Computer Science, Sharm el Sheik,
Egypt, January, 2009.
[6] Duffany, J.L., "Equivalence Class Subset Algorithm", International
Conference Computer Information Technology, Tokyo, Japan, May,
2009.
[7] http://mat.gsia.cmu.edu/COLOR/instances.html
[8] http://www.r-project.org
@article{"International Journal of Information, Control and Computer Sciences:59124", author = "Jeffrey L. Duffany", title = "Complexity Analysis of Some Known Graph Coloring Instances", abstract = "Graph coloring is an important problem in computer
science and many algorithms are known for obtaining reasonably
good solutions in polynomial time. One method of comparing
different algorithms is to test them on a set of standard graphs where
the optimal solution is already known. This investigation analyzes a
set of 50 well known graph coloring instances according to a set of
complexity measures. These instances come from a variety of
sources some representing actual applications of graph coloring
(register allocation) and others (mycieleski and leighton graphs) that
are theoretically designed to be difficult to solve. The size of the
graphs ranged from ranged from a low of 11 variables to a high of
864 variables. The method used to solve the coloring problem was
the square of the adjacency (i.e., correlation) matrix. The results
show that the most difficult graphs to solve were the leighton and the
queen graphs. Complexity measures such as density, mobility,
deviation from uniform color class size and number of block
diagonal zeros are calculated for each graph. The results showed that
the most difficult problems have low mobility (in the range of .2-.5)
and relatively little deviation from uniform color class size.", keywords = "graph coloring, complexity, algorithm.", volume = "4", number = "3", pages = "536-7", }