Minimum sum set coloring of trees and line graphs of trees
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 i...
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Artículo publishedVersion |
| Publicado: |
2011
|
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_0166218X_v159_n5_p288_Bonomo https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v159_n5_p288_Bonomo_oai |
| Aporte de: |
| id |
I28-R145-paper_0166218X_v159_n5_p288_Bonomo_oai |
|---|---|
| record_format |
dspace |
| spelling |
I28-R145-paper_0166218X_v159_n5_p288_Bonomo_oai2024-08-16 Bonomo, F. Durn, G. Marenco, J. Valencia-Pabon, M. 2011 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: non-preemptive 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. © 2010 Elsevier B.V. All rights reserved. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Marenco, J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf http://hdl.handle.net/20.500.12110/paper_0166218X_v159_n5_p288_Bonomo info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar Discrete Appl Math 2011;159(5):288-294 Graph coloring Line graphs of trees Minimum sum coloring Set-coloring Trees Graph colorings Line graph Minimum sum coloring Set-coloring Trees Coloring Graph theory Graphic methods Trees (mathematics) Minimum sum set coloring of trees and line graphs of trees info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v159_n5_p288_Bonomo_oai |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-145 |
| collection |
Repositorio Digital de la Universidad de Buenos Aires (UBA) |
| topic |
Graph coloring Line graphs of trees Minimum sum coloring Set-coloring Trees Graph colorings Line graph Minimum sum coloring Set-coloring Trees Coloring Graph theory Graphic methods Trees (mathematics) |
| spellingShingle |
Graph coloring Line graphs of trees Minimum sum coloring Set-coloring Trees Graph colorings Line graph Minimum sum coloring Set-coloring Trees Coloring Graph theory Graphic methods Trees (mathematics) Bonomo, F. Durn, G. Marenco, J. Valencia-Pabon, M. Minimum sum set coloring of trees and line graphs of trees |
| topic_facet |
Graph coloring Line graphs of trees Minimum sum coloring Set-coloring Trees Graph colorings Line graph Minimum sum coloring Set-coloring Trees Coloring Graph theory Graphic methods Trees (mathematics) |
| description |
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: non-preemptive 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. © 2010 Elsevier B.V. All rights reserved. |
| format |
Artículo Artículo publishedVersion |
| author |
Bonomo, F. Durn, G. Marenco, J. Valencia-Pabon, M. |
| author_facet |
Bonomo, F. Durn, G. Marenco, J. Valencia-Pabon, M. |
| author_sort |
Bonomo, F. |
| title |
Minimum sum set coloring of trees and line graphs of trees |
| title_short |
Minimum sum set coloring of trees and line graphs of trees |
| title_full |
Minimum sum set coloring of trees and line graphs of trees |
| title_fullStr |
Minimum sum set coloring of trees and line graphs of trees |
| title_full_unstemmed |
Minimum sum set coloring of trees and line graphs of trees |
| title_sort |
minimum sum set coloring of trees and line graphs of trees |
| publishDate |
2011 |
| url |
http://hdl.handle.net/20.500.12110/paper_0166218X_v159_n5_p288_Bonomo https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v159_n5_p288_Bonomo_oai |
| work_keys_str_mv |
AT bonomof minimumsumsetcoloringoftreesandlinegraphsoftrees AT durng minimumsumsetcoloringoftreesandlinegraphsoftrees AT marencoj minimumsumsetcoloringoftreesandlinegraphsoftrees AT valenciapabonm minimumsumsetcoloringoftreesandlinegraphsoftrees |
| _version_ |
1809356811871977472 |