Algorithms for the graph coloring problem
MetadataShow full item record
AbstractThe graph coloring problem is known to be in the class of NP-complete problems. Two approaches of solving the problem have been discussed in the past: (1) formulating the problem into a 0-1 integer programming model, which mathematically expresses the feasibility of applying given colors to a graph, and solving the model iteratively using an implicit enumerat ion algorithm; and (2) implicitly enumerating all possible assignments of colors to the vertices. For the first approach, a 0-1 goal programming model is proposed , and an algorithm is constructed to solve the model. The algorithm requires a huge amount of storage; therefore, it is considered to be inferior to existing algorithms which utilize the second approach. However, the theoretical development of the model and the algorithm are discussed at length. For the second approach, a branch-and-bound algorithm is constructed which implicitly enumerates all possible assignments of colors to the vertices. The algorithm is further improved by incorporating a separation method called the range cutting method. The cutting method is shown experimentally to be effective for the graph coloring problem, and therefore, is extensively discussed in application to the integer programming problem. In an attempt to enhance the performance of the branch-and-bound algorithms, a heuristic algorithm modified from t he color-degree algorithm is constructed to generate a range for the optimal solution of the graph coloring problem . The modified algorithm gene rates much narrower ranges than the color-degree algorithm does, thus enhancing the efficiency of the graph coloring algorithms.
Bibliography: p. 75-77.
CitationYen, Y. (1987). Algorithms for the graph coloring problem (Unpublished master's thesis). University of Calgary, Calgary, AB. doi:10.11575/PRISM/21320
University of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.