HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Coloring an interval graph with weights

Submitted by: @import:stackexchange-cs··
0
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?

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

Context

StackExchange Computer Science Q#118760, answer score: 2

Revisions (0)

No revisions yet.