Algorithms for the graph coloring problem

Simple item page
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.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.identifier.citationYen, Y. (1987). Algorithms for the graph coloring problem (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca. doi:10.11575/PRISM/21320en_US
dc.identifier.doihttp://dx.doi.org/10.11575/PRISM/21320
dc.identifier.isbn0315380942en
dc.identifier.lccQA 611 Y44 1987en
dc.identifier.urihttp://hdl.handle.net/1880/23917
dc.language.isoeng
dc.publisher.institutionUniversity of Calgaryen
dc.publisher.placeCalgaryen
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
thesis.degree.disciplineComputer Science
thesis.degree.grantorUniversity of Calgary
thesis.degree.nameMaster of Science (MSc)
ucalgary.item.requestcopytrue
ucalgary.thesis.accessionTheses Collection 58.002:Box 644 520535162
ucalgary.thesis.notesoffsiteen
ucalgary.thesis.uarcreleaseyen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
thesis_Yen_1987.pdf
Size:
31.46 MB
Format:
Adobe Portable Document Format
Description:
Thesis
Download
Collections
Legacy Theses