Back to search

Lethbridge, Alta : University of Lethbridge, Dept. of Mathematics and Computer Science

Algorithms for weighted coloring problems

Abstract

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.

Degree

thesis:*
Level thesis:degree_level
Ph.D
Grantor dc:publisher
Lethbridge, Alta : University of Lethbridge, Dept. of Mathematics and Computer Science
Year dc:date.issued
2017

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Dahal, Ram Sewak
  • University of Lethbridge. Faculty of Arts and Science
Advisors dc:contributor.supervisor
  • Benkoczi, Robert
  • Gaur, Daya

Subjects

dc:subject × 6

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10133/4851

Chain of custody

source
Harvested from
University of Lethbridge
Base URL
opus.uleth.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Dahal, Ram Sewak; University of Lethbridge. Faculty of Arts and Science. Algorithms for weighted coloring problems. Ph.D thesis, Lethbridge, Alta : University of Lethbridge, Dept. of Mathematics and Computer Science, 2017. https://hdl.handle.net/10133/4851