On the Minimum Sum Coloring of P 4-Sparse Graphs
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...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
2012
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 02447caa a22003497a 4500 | ||
|---|---|---|---|
| 001 | PAPER-9171 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518203903.0 | ||
| 008 | 140217s2012 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-84869869619 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Bonomo, F. | |
| 245 | 1 | 3 | |a On the Minimum Sum Coloring of P 4-Sparse Graphs |
| 260 | |c 2012 | ||
| 270 | 1 | 0 | |m Bonomo, F.; IMAS-CONICET, Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina; email: fbonomo@dc.uba.ar |
| 506 | |2 openaire |e Política editorial | ||
| 520 | 3 | |a 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. |l eng | |
| 536 | |a Article in Press | ||
| 593 | |a IMAS-CONICET, Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina | ||
| 593 | |a LIPN, Université Paris-Nord, 99 Av. J.-B. Clément, Villetaneuse, 93430, France | ||
| 690 | 1 | 0 | |a GRAPH COLORING |
| 690 | 1 | 0 | |a MINIMUM SUM COLORING |
| 690 | 1 | 0 | |a P 4-SPARSE GRAPHS |
| 700 | 1 | |a Valencia-Pabon, M. | |
| 773 | 0 | |d 2012 |h pp. 1-12 |p Graphs Comb. |x 09110119 |w (AR-BaUEN)CENRE-4859 |t Graphs and Combinatorics | |
| 856 | 4 | 1 | |u http://www.scopus.com/inward/record.url?eid=2-s2.0-84869869619&partnerID=40&md5=3d2acc8d89d8f5404397396cbc43cf41 |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1007/s00373-012-1269-5 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_09110119_v_n_p1_Bonomo |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_09110119_v_n_p1_Bonomo |y Registro en la Biblioteca Digital |
| 961 | |a paper_09110119_v_n_p1_Bonomo |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 999 | |c 70124 | ||