Artículo
Bonomo, F.; Valencia-Pabon, M. "On the Minimum Sum Coloring of P 4-Sparse Graphs" (2012) Graphs and Combinatorics:1-12
Estamos trabajando para incorporar este artículo al repositorio
Consulte la política de Acceso Abierto del editor
Abstract:
In this paper, we study the minimum sum coloring (MSC) problem on P 4-sparse graphs. In the MSC problem, we aim to assign natural numbers to vertices of a graph such that adjacent vertices get different numbers, and the sum of the numbers assigned to the vertices is minimum. Based in the concept of maximal sequence associated with an optimal solution of the MSC problem of any graph, we show that there is a large sub-family of P 4-sparse graphs for which the MSC problem can be solved in polynomial time. Moreover, we give a parameterized algorithm and a 2-approximation algorithm for the MSC problem on general P 4-sparse graphs. © 2012 Springer Japan.
Registro:
| Documento: | Artículo |
| Título: | On the Minimum Sum Coloring of P 4-Sparse Graphs |
| Autor: | Bonomo, F.; Valencia-Pabon, M. |
| Filiación: | IMAS-CONICET, Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina LIPN, Université Paris-Nord, 99 Av. J.-B. Clément, Villetaneuse, 93430, France |
| Idioma: | Inglés |
| Palabras clave: | Graph coloring; Minimum sum coloring; P 4-sparse graphs |
| Año: | 2012 |
| Página de inicio: | 1 |
| Página de fin: | 12 |
| DOI: | http://dx.doi.org/10.1007/s00373-012-1269-5 |
| Título revista: | Graphs and Combinatorics |
| Título revista abreviado: | Graphs Comb. |
| ISSN: | 09110119 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_09110119_v_n_p1_Bonomo |
Citas:
---------- APA ----------
Bonomo, F. & Valencia-Pabon, M. (2012) . On the Minimum Sum Coloring of P 4-Sparse Graphs. Graphs and Combinatorics, 1-12.http://dx.doi.org/10.1007/s00373-012-1269-5
---------- CHICAGO ----------
Bonomo, F., Valencia-Pabon, M. "On the Minimum Sum Coloring of P 4-Sparse Graphs" . Graphs and Combinatorics (2012) : 1-12.http://dx.doi.org/10.1007/s00373-012-1269-5
---------- MLA ----------
Bonomo, F., Valencia-Pabon, M. "On the Minimum Sum Coloring of P 4-Sparse Graphs" . Graphs and Combinatorics, 2012, pp. 1-12.http://dx.doi.org/10.1007/s00373-012-1269-5
---------- VANCOUVER ----------
Bonomo, F., Valencia-Pabon, M. On the Minimum Sum Coloring of P 4-Sparse Graphs. Graphs Comb. 2012:1-12.http://dx.doi.org/10.1007/s00373-012-1269-5
