{"title":"Complexity Analysis of Some Known Graph Coloring Instances","authors":"Jeffrey L. Duffany","country":null,"institution":"","volume":39,"journal":"International Journal of Electrical and Computer Engineering","pagesStart":392,"pagesEnd":399,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/10062","abstract":"Graph coloring is an important problem in computer\r\nscience and many algorithms are known for obtaining reasonably\r\ngood solutions in polynomial time. One method of comparing\r\ndifferent algorithms is to test them on a set of standard graphs where\r\nthe optimal solution is already known. This investigation analyzes a\r\nset of 50 well known graph coloring instances according to a set of\r\ncomplexity measures. These instances come from a variety of\r\nsources some representing actual applications of graph coloring\r\n(register allocation) and others (mycieleski and leighton graphs) that\r\nare theoretically designed to be difficult to solve. The size of the\r\ngraphs ranged from ranged from a low of 11 variables to a high of\r\n864 variables. The method used to solve the coloring problem was\r\nthe square of the adjacency (i.e., correlation) matrix. The results\r\nshow that the most difficult graphs to solve were the leighton and the\r\nqueen graphs. Complexity measures such as density, mobility,\r\ndeviation from uniform color class size and number of block\r\ndiagonal zeros are calculated for each graph. The results showed that\r\nthe most difficult problems have low mobility (in the range of .2-.5)\r\nand relatively little deviation from uniform color class size.","references":null,"publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 39, 2010"}