dc.contributor.advisor Colijn, Anton W. dc.contributor.author Yen, Yung-Hsien dc.date.accessioned 2005-07-21T21:54:41Z dc.date.available 2005-07-21T21:54:41Z dc.date.issued 1987 dc.identifier.citation Yen, Y. (1987). Algorithms for the graph coloring problem (Unpublished master's thesis). University of Calgary, Calgary, AB. doi:10.11575/PRISM/21320 en_US dc.identifier.isbn 0315380942 en dc.identifier.uri http://hdl.handle.net/1880/23917 dc.description Bibliography: p. 75-77. en dc.description.abstract The 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. dc.format.extent x, 77 leaves ; 30 cm. en dc.language.iso eng dc.rights 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. dc.subject.lcc QA 611 Y44 1987 en dc.subject.lcsh Graph theory dc.subject.lcsh Algebraic topology dc.title Algorithms for the graph coloring problem dc.type master thesis dc.publisher.institution University of Calgary en dc.identifier.doi http://dx.doi.org/10.11575/PRISM/21320 thesis.degree.name Master of Science thesis.degree.name MS thesis.degree.name MSc thesis.degree.discipline Computer Science thesis.degree.grantor University of Calgary dc.identifier.lcc QA 611 Y44 1987 en dc.publisher.place Calgary en ucalgary.thesis.notes offsite en ucalgary.thesis.uarcrelease y en ucalgary.item.requestcopy true ucalgary.thesis.accession Theses Collection 58.002:Box 644 520535162
﻿

This item appears in the following Collection(s)

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.