Minimum sum set coloring of trees and line graphs of trees
2011, Discrete Applied Mathematics 159 (5), 288-294, 2011Citas: 6
Agregar PDF Plots Conexiones
Autor(es)
Flavia Bonomo and Guillermo Durán and Javier Marenco and Mario Valencia-Pabon
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: 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.
Plot de citas
Citas
| # | Title | Year | Source | Authors | |
|---|---|---|---|---|---|
| 1 | Algorithms for the minimum sum coloring problem: a review | 2017 | Artificial Intelligence Review | Y Jin, JP Hamiez, JK Hao | |
| 2 | Hybrid evolutionary search for the minimum sum coloring problem of graphs | 2016 | Information Sciences | Y Jin, JK Hao | |
| 3 | An effective heuristic algorithm for sum coloring of graphs | 2012 | Computers & Operations Research | Q Wu, JK Hao | |
| 4 | Solving the minimum sum coloring problem via binary quadratic programming | 2013 | arXiv preprint arXiv:1304.5876 | Y Wang, JK Hao, F Glover, Z Lü | |
| 5 | Improved lower bounds for sum coloring via clique decomposition | 2013 | arXiv preprint arXiv:1303.6761 | Q Wu, JK Hao | |
| 6 | On integrating an iterated variable neighborhood search within a bi-objective genetic algorithm: Sum coloring of graphs case application | 2018 | Electronic Notes in Discrete Mathematics | O Harrabi, JC Siala, H Bouziri |
Citas de Scrapping
| # | Año | #Citas | Título | Autores | Journal | Editor |
|---|---|---|---|---|---|---|
| 1 | 2017 | 53 | Algorithms for the minimum sum coloring problem: a review | Y Jin, JP Hamiez, JK Hao | Artificial Intelligence Review, 2017 | Springer |
| 2 | 2016 | 54 | Hybrid evolutionary search for the minimum sum coloring problem of graphs | Y Jin, JK Hao | Information Sciences, 2016 | Elsevier |
| 3 | 2012 | 44 | An effective heuristic algorithm for sum coloring of graphs | Q Wu, JK Hao | Computers & Operations Research, 2012 | Elsevier |
| 4 | 1304 | 23 | Solving the minimum sum coloring problem via binary quadratic programming | Y Wang, JK Hao, F Glover, Z Lü | arXiv preprint arXiv:1304.5876, 2013 | arxiv.org |
| 5 | 1303 | 21 | Improved lower bounds for sum coloring via clique decomposition | Q Wu, JK Hao | arXiv preprint arXiv:1303.6761, 2013 | arxiv.org |
| 6 | 2018 | 2 | On integrating an iterated variable neighborhood search within a bi-objective genetic algorithm: Sum coloring of graphs case application | O Harrabi, JC Siala, H Bouziri | Electronic Notes in Discrete Mathematics, 2018 | Elsevier |