patternMinor
Coloring an interval graph with weights
Viewed 0 times
coloringgraphwithweightsinterval
Problem
I have an interval graph $G=(V,E)$ and a set of colors $C=\{c_1,c_2,...,c_m\}$, when a color $c_i$ is assigned to a vertex $v_j$, we have a score $u_{ij}\geq 0$. The objective is to find a coloring of $G$ with at most $m$ colors that maximizes the total score (sum of the scores of the vertices).
Do you know about any results in the literature that may help me to find the complexity of this problem?
Do you know about any results in the literature that may help me to find the complexity of this problem?
Solution
The sum coloring problem can be reduced to this problem by having $n$ possible colors with weights $u_{ij} = n - i$. Sum coloring is NP-hard for interval graphs.
Source: https://en.wikipedia.org/wiki/Sum_coloring
Source: https://en.wikipedia.org/wiki/Sum_coloring
Context
StackExchange Computer Science Q#118760, answer score: 2
Revisions (0)
No revisions yet.