Minimum sum set coloring of trees and line graphs of trees

Mostrar todas las versiones(3)

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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bonomo, F., Durn, G., Marenco, J., Valencia-Pabon, M.
Formato: JOUR
Materias:
Graph coloring
Line graphs of trees
Minimum sum coloring
Set-coloring
Trees
Graph colorings
Line graph
Coloring
Graph theory
Graphic methods
Trees (mathematics)
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_0166218X_v159_n5_p288_Bonomo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_0166218X_v159_n5_p288_Bonomo
record_format dspace
spelling todo:paper_0166218X_v159_n5_p288_Bonomo2023-10-03T15:03:38Z Minimum sum set coloring of trees and line graphs of trees Bonomo, F. Durn, G. Marenco, J. Valencia-Pabon, M. 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) 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_0166218X_v159_n5_p288_Bonomo
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (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 JOUR
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
url http://hdl.handle.net/20.500.12110/paper_0166218X_v159_n5_p288_Bonomo
work_keys_str_mv AT bonomof minimumsumsetcoloringoftreesandlinegraphsoftrees
AT durng minimumsumsetcoloringoftreesandlinegraphsoftrees
AT marencoj minimumsumsetcoloringoftreesandlinegraphsoftrees
AT valenciapabonm minimumsumsetcoloringoftreesandlinegraphsoftrees
_version_ 1807321222425346048

Ejemplares similares