Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
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 P4-Sparse Graphs
Autor:Bonomo, F.; Valencia-Pabon, M.
Filiación:IMAS-CONICET, Departamento de Computación, Universidad de Buenos Aires, Buenos Aires, Argentina
LIPN, Université Paris-Nord, 99 Av. J.-B. Clément, 93430 Villetaneuse, France
Palabras clave:Graph coloring; Minimum sum coloring; P4-sparse graphs
Año:2014
Volumen:30
Número:2
Página de inicio:303
Página de fin:314
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_v30_n2_p303_Bonomo

Referencias:

  • Bar-Noy, A., Bellare, M., Halldórsson, M.M., Shachnai, H., Tamir, T., On chromatic sums and distributed resource allocation (1998) Inf. Comput., 140 (2), pp. 183-202
  • Bar-Noy, A., Kortsarz, G., Minimum color sum of bipartite graphs (1998) J. Algorithms, 28 (2), pp. 339-365
  • Bonomo, F., Valencia-Pabon, M., Minimum sum coloring of P4-sparse graphs (2009) Proceedings pf V Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS), 35, pp. 293-298. , Electronic Notes in Discrete Mathematics, Elsevier, Amsterdam
  • Feige, U., Lovász, L., Tetali, P., Approximating min sum set cover (2004) Algorithmica, 40 (4), pp. 219-234
  • Giaro, K., Janczewski, R., Kubale, M., Malafiejski, M., A 27/26-approximation algorithm for the chromatic sum coloring of bipartite graphs (2002) Proceedings of 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), 2462, pp. 135-145. , Lecture Notes in Computer Science, Springer, Berlin
  • Halldórsson, M.M., Kortsarz, G., Shachnai, H., Sum coloring interval and k-claw free graphs with application to scheduling dependent jobs (2003) Algorithmica, 37 (3), pp. 187-209
  • Hoààng, C.T., (1985) Perfect graphs, , Thesis, School of Computer Science, McGill University
  • Jamison, B., Olariu, S., P4-reducible graphs-a class of uniquely tree-representable graphs (1984) Discret. Math., 51, pp. 35-39
  • Jamison, B., Olariu, S., Recognizing P4-sparse graphs in linear time (1992) SIAM J. Comput., 21, pp. 381-406
  • Jamison, B., Olariu, S., A tree representation for P4-sparse graphs (1992) Discret. Appl. Math., 35, pp. 115-129
  • Jansen, K., Complexity results for the optimum cost chromatic partition problem (1997) Proceedings of 24th International Colloquium on Automata, Languages and Programming (ICALP), 1256, pp. 27-737. , Lecture Notes in Computer Science,Springer, Berlin
  • Kubick, E., (1989) The chromatic sum of a graph, , Thesis, Western Michigan University
  • Kubicka, E., Schwenk, A.J., An introduction to chromatic sums (1989) Proceedings of 17th ACM Annual Computer Science Conference, pp. 39-45
  • Nicoloso, S., Sarrafzadeh, M., Song, X., On the sum coloring problem on interval graphs (1999) Algorithmica, 23 (2), pp. 109-126
  • Salavatipour, M., (2000) On sum coloring of graphs, , Master's thesis, Department of Computer Science, University of Toronto
  • Szkaliczki, T., Routing with minimum wire length in the dogleg-free Manhattan model is NP-complete (1999) SIAM J. Comput., 29 (1), pp. 274-287

Citas:

---------- APA ----------
Bonomo, F. & Valencia-Pabon, M. (2014) . On the Minimum Sum Coloring of P4-Sparse Graphs. Graphs and Combinatorics, 30(2), 303-314.
http://dx.doi.org/10.1007/s00373-012-1269-5
---------- CHICAGO ----------
Bonomo, F., Valencia-Pabon, M. "On the Minimum Sum Coloring of P4-Sparse Graphs" . Graphs and Combinatorics 30, no. 2 (2014) : 303-314.
http://dx.doi.org/10.1007/s00373-012-1269-5
---------- MLA ----------
Bonomo, F., Valencia-Pabon, M. "On the Minimum Sum Coloring of P4-Sparse Graphs" . Graphs and Combinatorics, vol. 30, no. 2, 2014, pp. 303-314.
http://dx.doi.org/10.1007/s00373-012-1269-5
---------- VANCOUVER ----------
Bonomo, F., Valencia-Pabon, M. On the Minimum Sum Coloring of P4-Sparse Graphs. Graphs Comb. 2014;30(2):303-314.
http://dx.doi.org/10.1007/s00373-012-1269-5