Minimum sum set coloring of trees and line graphs of trees

BONOMO, FLAVIA; DURAN, GUILLERMO ALFREDO; MARENCO, JAVIER; VALENCIA-PABON, MARIO

DISCRETE APPLIED MATHEMATICS

ELSEVIER SCIENCE BV

Lugar: Amsterdam; Año: 2011 vol. 159 p. 288 - 294

0166-218X

In this paper, we study the minimum sum set coloring (MSSC) problem which consists inassigning a set of x(v) positive integers to each vertex v of a graph so that the intersectionof sets assigned to adjacent vertices is empty and the sum of the assigned set of numbersto each vertex of the graph is minimum. The MSSC problem occurs in two versions: nonpreemptiveand preemptive. We show that the MSSC problem is strongly NP-hard both inthe preemptive case on trees and in the non-preemptive case in line graphs of trees. Finally,we give exact parameterized algorithms for these two versions on trees and line graphs oftrees.