congresos y reuniones científicas
Minimum Sum Set Coloring on some Subclasses of Block Graphs
BONOMO, FLAVIA; DURÁN, GUILLERMO; MARENCO, JAVIER; VALENCIA-PABON, MARIO
Workshop; Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW); 2009
École Polytechnique and CNAM
In this work we study the Minimum Sum Set Coloring Problem (MSSCP) which consists in assign a set of w(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.