Autor(es)

Flavia Bonomo and Guillermo Durán and Javier Marenco and Mario Valencia-Pabon

URL Pública

Abstract

In this work we study the Minimum Sum Set Coloring Problem (MSSCP) which consists in assign a set of ω (v) positive integers to each vertex v of a graph so that the intersection of sets assigned to adjacent vertices is empty and the sum of the assigned set of numbers to each vertex of the graph is minimum. This problem generalizes the well known Minimum Sum Coloring Problem, which is solvable in polynomial time on block graphs. We study two versions of the MSSCP (preemptive and non-preemptive) on two subclasses of block graphs: trees and line graphs of trees. This allows us to show that both versions of the problem are NP-complete on block graphs. We also find polynomial-time algorithms for the MSSCP under certain conditions.