Navegar

Colección

Datos Estadísticas

Artículo

Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro 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 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.

Registro:

Documento: Artículo
Título:Minimum sum set coloring of trees and line graphs of trees
Autor:Bonomo, F.; Durn, G.; Marenco, J.; Valencia-Pabon, M.
Filiación:CONICET, Argentina
Departamento de Computacin, FCEN, Universidad de Buenos Aires, Argentina
Departamento de Matemtica, FCEN, Universidad de Buenos Aires, Argentina
Departamento de Ingeniera Industrial, FCFM, Universidad de Chile, Chile
Instituto de Ciencias, Universidad Nacional de General Sarmiento, Argentina
LIPN, Universit Paris-Nord, France
Palabras clave: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)
Año:2011
Volumen:159
Número:5
Página de inicio:288
Página de fin:294
DOI: http://dx.doi.org/10.1016/j.dam.2010.11.018
Título revista:Discrete Applied Mathematics
Título revista abreviado:Discrete Appl Math
ISSN:0166218X
CODEN:DAMAD
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_0166218X_v159_n5_p288_Bonomo.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v159_n5_p288_Bonomo

Referencias:

  • Bar-Noy, A., Bellare, M., Halldrsson, M.M., Shachnai, H., Tamir, T., On chromatic sums and distributed resource allocation (1998) Information and Computation, 140 (2), pp. 183-202
  • Bar-Noy, A., Kortsarz, G., Minimum color sum of bipartite graphs (1998) Journal of Algorithms, 28 (2), pp. 339-365
  • Bar-Noy, A., Halldrsson, M.M., Kortsarz, G., Salman, R., Shachnai, H., Sum multicoloring of graphs (2000) Journal of Algorithms, 37 (2), pp. 422-450
  • Cardinal, J., Ravelomanana, V., Valencia-Pabon, M., Minimum sum edge coloring of multicycles (2010) Discrete Applied Mathematics, 158 (12), pp. 1216-1223
  • Feige, U., Lovsz, L., Tetali, P., Approximating min sum set cover (2004) Algorithmica, 40 (4), pp. 219-234
  • Gandhi, R., Mestre, J., Combinatorial algorithms for data migration to minimize average completion time (2009) Algorithmica, 54 (1), pp. 54-71
  • Giaro, K., Janczewski, R., Kubale, M., Malafiejski, M., A 2726-approximation algorithm for the chromatic sum coloring of bipartite graphs (2002) Proc. of APPROX'02 LNCS, 2486, pp. 135-145. , Springer-Verlag
  • Giaro, K., Kubale, M., Edge-chromatic sum of trees and bounded cyclicity graphs (2000) Information Processing Letters, 75 (12), pp. 65-69
  • Halldrsson, M.M., Kortsarz, G., Proskurowski, A., Salman, R., Shachnai, H., Telle, J.A., Multi-coloring trees (2002) Information and Computation, 180 (2), pp. 113-129
  • Halldrsson, 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
  • Halldrsson, M.M., Kortsarz, G., Sviridenko, M., Min sum edge coloring in multigraphs via configuration LP (2008) Proc. of IPCO'08 LNCS, 5035, pp. 359-373
  • Jansen, K., Complexity results for the optimum cost chromatic partition problem (1997) Proc. of ICALP'97 LNCS, 1256, pp. 727-737
  • Kubicka, E., (1989) The Chromatic Sum of A Graph, , Ph.D. Thesis, Western Michigan University
  • Kubicka, E., Schwenk, A.J., An introduction to chromatic sums (1989) Proc. of the 17th ACM Annual Comput. Sci. Conf., pp. 39-45
  • Marx, D., The complexity of tree multicolorings (2002) Proc. of MFCS'02 LNCS, 2420, pp. 532-542
  • Marx, D., Minimum sum multicoloring on the edges of trees (2006) Theoretical Computer Science, 361 (23), pp. 133-149
  • Marx, D., Complexity results for minimum sum edge coloring (2009) Discrete Applied Mathematics, 157 (5), pp. 1034-1045
  • Nicoloso, S., Sarrafzadeh, M., Song, X., On the sum coloring problem on interval graphs (1999) Algorithmica, 23 (2), pp. 109-126
  • Papadimitriou, C.H., (1994) Computational Complexity, , Addison-Wesley Reading, MA
  • Salavatipour, M., On sum coloring of graphs (2003) Discrete Applied Mathematics, 127 (3), pp. 477-488
  • Szkaliczki, T., Routing with minimum wire length in the dogleg-free manhattan model is NP-complete (1999) SIAM Journal on Computing, 29 (1), pp. 274-287
  • Zhou, X., Nishizeki, T., Algorithm for the cost edge-coloring of trees (2004) Journal of Combinatorial Optimization, 8 (1), pp. 97-108

Citas:

---------- APA ----------
Bonomo, F., Durn, G., Marenco, J. & Valencia-Pabon, M. (2011) . Minimum sum set coloring of trees and line graphs of trees. Discrete Applied Mathematics, 159(5), 288-294.
http://dx.doi.org/10.1016/j.dam.2010.11.018
---------- CHICAGO ----------
Bonomo, F., Durn, G., Marenco, J., Valencia-Pabon, M. "Minimum sum set coloring of trees and line graphs of trees" . Discrete Applied Mathematics 159, no. 5 (2011) : 288-294.
http://dx.doi.org/10.1016/j.dam.2010.11.018
---------- MLA ----------
Bonomo, F., Durn, G., Marenco, J., Valencia-Pabon, M. "Minimum sum set coloring of trees and line graphs of trees" . Discrete Applied Mathematics, vol. 159, no. 5, 2011, pp. 288-294.
http://dx.doi.org/10.1016/j.dam.2010.11.018
---------- VANCOUVER ----------
Bonomo, F., Durn, G., Marenco, J., Valencia-Pabon, M. Minimum sum set coloring of trees and line graphs of trees. Discrete Appl Math. 2011;159(5):288-294.
http://dx.doi.org/10.1016/j.dam.2010.11.018