| Author | dc.contributor.author | Bonomo, Flavia | |
| Author | dc.contributor.author | Durán Maggiolo, Guillermo | es_CL |
| Author | dc.contributor.author | Marenco, Javier | es_CL |
| Author | dc.contributor.author | Valencia Pabon, Mario | es_CL |
| Admission date | dc.date.accessioned | 2011-10-18T15:10:57Z | |
| Available date | dc.date.available | 2011-10-18T15:10:57Z | |
| Publication date | dc.date.issued | 2011 | |
| Cita de ítem | dc.identifier.citation | Discrete Applied Mathematics 159 (2011) 288–294 | es_CL |
| Identifier | dc.identifier.other | doi:10.1016/j.dam.2010.11.018 | |
| Identifier | dc.identifier.uri | https://repositorio.uchile.cl/handle/2250/125484 | |
| Abstract | dc.description.abstract | In this paper, we study the minimum sum set coloring (MSSC) problem which consists in
assigning a set of x(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. The MSSC problem occurs in two versions: nonpreemptive
and preemptive. We show that the MSSC problem is strongly NP-hard both in
the 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 of
trees. | es_CL |
| Patrocinador | dc.description.sponsorship | Partially supported by ANPCyT PICT-2007-00518 (Argentina), BQR-2008 Université Paris-Nord Grant (France), and Math-AmSud Project 10MATH-04
(France-Argentina-Brazil). | es_CL |
| Lenguage | dc.language.iso | en | es_CL |
| Publisher | dc.publisher | Elsevier | es_CL |
| Keywords | dc.subject | Graph coloring | es_CL |
| Título | dc.title | Minimum sum set coloring of trees and line graphs of trees | es_CL |
| Document type | dc.type | Artículo de revista | |
