Show simple item record

dc.contributor.advisorColijn, Anton W.
dc.contributor.authorYen, Yung-Hsien
dc.date.accessioned2005-07-21T21:54:41Z
dc.date.available2005-07-21T21:54:41Z
dc.date.issued1987
dc.identifier.citationYen, Y. (1987). Algorithms for the graph coloring problem (Unpublished master's thesis). University of Calgary, Calgary, AB. doi:10.11575/PRISM/21320en_US
dc.identifier.isbn0315380942en
dc.identifier.urihttp://hdl.handle.net/1880/23917
dc.descriptionBibliography: p. 75-77.en
dc.description.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.
dc.format.extentx, 77 leaves ; 30 cm.en
dc.language.isoeng
dc.rightsUniversity 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.lccQA 611 Y44 1987en
dc.subject.lcshGraph theory
dc.subject.lcshAlgebraic topology
dc.titleAlgorithms for the graph coloring problem
dc.typemaster thesis
dc.publisher.institutionUniversity of Calgaryen
dc.identifier.doihttp://dx.doi.org/10.11575/PRISM/21320
thesis.degree.nameMaster of Science
thesis.degree.nameMS
thesis.degree.nameMSc
thesis.degree.disciplineComputer Science
thesis.degree.grantorUniversity of Calgary
dc.identifier.lccQA 611 Y44 1987en
dc.publisher.placeCalgaryen
ucalgary.thesis.notesoffsiteen
ucalgary.thesis.uarcreleaseyen
ucalgary.item.requestcopytrue
ucalgary.thesis.accessionTheses Collection 58.002:Box 644 520535162


Files in this item

Thumbnail
Embargoed until: 2200-01-01

This item appears in the following Collection(s)

Show simple item record

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.