Show simple item record

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. 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. en_US
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


Files in this item

This item appears in the following Collection(s)

Show simple item record