dc.contributor.supervisor Benkoczi, Robert dc.contributor.supervisor Gaur, Daya dc.contributor.author Dahal, Ram Sewak dc.contributor.author University of Lethbridge. Faculty of Arts and Science dc.date.accessioned 2017-05-29T21:18:28Z dc.date.available 2017-05-29T21:18:28Z dc.date.issued 2017 dc.identifier.uri https://hdl.handle.net/10133/4851 dc.description.abstract In this thesis, we studied a generalization of vertex coloring problem (VCP). A classical VCP is an assignment of colors to the vertices of a given graph such that no two adjacent vertices receive the same color. The objective is to find a coloring with the minimum number of colors. In the first part of the thesis, we studied the weighted version of the problem, where vertices have non-negative weights. In a weighted vertex coloring problem (WVCP) the cost of each color depends on the weights of the vertices assigned to that color and equals the maximum of these weights. Furthermore, in WVCP, the adjacent vertices are assigned different colors, and the objective is to minimize the total cost of all the colors used. We studied WVCP and proposed an O(n^2 log n) time algorithm for binary trees. Additionally, we studied WVCP in cactus paths. We proposed sub-quadratic and quadratic time algorithms for cactus paths. en_US We studied a min-max regret version of the robust optimization where the weight of each vertex v is in the interval [w v , w v ]. The objective of is to find a coloring that has the minimum regret value. We proposed a linear time algorithm for robust coloring on bipartite graphs with uniform upper bound and arbitrary lower bound weights on the vertices. We also gave an integer linear programming (ILP) for the robust weighted vertex coloring problem (RWVCP). We solved a relaxation of the ILP formulation using column generation. We also gave an algorithm based on the branch and price method. Lastly, we performed experiments to study the quality of our algorithms. dc.description.sponsorship School of graduate studies, University of Lethbridge, PIMS, NSERC en_US dc.language.iso en_US en_US dc.publisher Lethbridge, Alta : University of Lethbridge, Dept. of Mathematics and Computer Science en_US dc.relation.ispartofseries Thesis (University of Lethbridge. Faculty of Arts and Science) en_US dc.subject binary trees en_US dc.subject cactus paths en_US dc.subject deterministic weights en_US dc.subject minimum regret en_US dc.subject robust weighted vertex coloring problem en_US dc.subject weighted vertex coloring problem en_US dc.title Algorithms for weighted coloring problems en_US dc.type Thesis en_US dc.publisher.faculty Arts and Science en_US dc.publisher.department Department of Mathematics and Computer Science en_US dc.degree.level Ph.D en_US dc.proquest.subject 0984 en_US dc.proquest.subject 0364 en_US dc.proquestyes Yes en_US dc.embargo No en_US
﻿