Algorithms for weighted coloring problems

Thumbnail Image
Date
2017
Authors
Dahal, Ram Sewak
University of Lethbridge. Faculty of Arts and Science
Journal Title
Journal ISSN
Volume Title
Publisher
Lethbridge, Alta : University of Lethbridge, Dept. of Mathematics and Computer Science
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.
Description
Keywords
binary trees , cactus paths , deterministic weights , minimum regret , robust weighted vertex coloring problem , weighted vertex coloring problem
Citation