Algorithms for weighted coloring problems

Simple item page
dc.contributor.authorDahal, Ram Sewak
dc.contributor.authorUniversity of Lethbridge. Faculty of Arts and Science
dc.contributor.supervisorBenkoczi, Robert
dc.contributor.supervisorGaur, Daya
dc.date.accessioned2017-05-29T21:18:28Z
dc.date.available2017-05-29T21:18:28Z
dc.date.issued2017
dc.degree.levelPh.Den_US
dc.description.abstractIn 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.sponsorshipSchool of graduate studies, University of Lethbridge, PIMS, NSERCen_US
dc.embargoNoen_US
dc.identifier.urihttps://hdl.handle.net/10133/4851
dc.language.isoen_USen_US
dc.proquest.subject0984en_US
dc.proquest.subject0364en_US
dc.proquestyesYesen_US
dc.publisherLethbridge, Alta : University of Lethbridge, Dept. of Mathematics and Computer Scienceen_US
dc.publisher.departmentDepartment of Mathematics and Computer Scienceen_US
dc.publisher.facultyArts and Scienceen_US
dc.relation.ispartofseriesThesis (University of Lethbridge. Faculty of Arts and Science)en_US
dc.subjectbinary treesen_US
dc.subjectcactus pathsen_US
dc.subjectdeterministic weightsen_US
dc.subjectminimum regreten_US
dc.subjectrobust weighted vertex coloring problemen_US
dc.subjectweighted vertex coloring problemen_US
dc.titleAlgorithms for weighted coloring problemsen_US
dc.typeThesisen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
DAHAL_RAM_PHD_2017.pdf
Size:
894.73 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
3.25 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Arts and Science, Faculty of
University of Lethbridge Theses