Navegar

Colección

Datos Estadísticas

Artículo

La versión final de este artículo es de uso interno de la institución.
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

In this note, we use a reduction by Cornaz and Jost from the graph (max-)coloring problem to the maximum (weighted) stable set problem in order to characterize new graph classes where the graph coloring problem and the more general max-coloring problem can be solved in polynomial time. © 2013 Elsevier B.V.

Registro:

Documento: Artículo
Título:A note on the Cornaz-Jost transformation to solve the graph coloring problem
Autor:Bonomo, F.; Giandomenico, M.; Rossi, F.
Filiación:IMAS-CONICET and Departamento de Computación, FCEN, Universidad de Buenos Aires, Buenos Aires, Argentina
Dipartimento di Informatica, Università di LÊAquila, LE'Aquila, Italy
Palabras clave:Computational complexity; Graph coloring problem; Graph operators; Max-coloring problem; Polynomial-time algorithm; Coloring problems; Graph class; Graph coloring problem; Max-coloring; Polynomial-time; Polynomial-time algorithms; Stable set problems; Algorithms; Computational complexity; Polynomial approximation; Graph theory
Año:2013
Volumen:113
Número:18
Página de inicio:649
Página de fin:652
DOI: http://dx.doi.org/10.1016/j.ipl.2013.05.014
Título revista:Information Processing Letters
Título revista abreviado:Inf. Process. Lett.
ISSN:00200190
CODEN:IFPLA
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v113_n18_p649_Bonomo

Referencias:

  • Brandstädt, A., Lozin, V., Mosca, R., Independent sets of maximum weight in apple-free graphs (2010) SIAM Journal on Discrete Mathematics, 24 (1), pp. 239-254
  • Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R., The strong perfect graph theorem (2006) Annals of Mathematics, 164 (1), pp. 51-229
  • Cornaz, D., Jost, V., A one-to-one correspondence between colorings and stable sets (2008) Operations Research Letters, 36 (6), pp. 673-676
  • De Werra, D., Demange, M., Escoffier, B., Monnot, J., Paschos, V., Weighted coloring on planar, bipartite and split graphs: Complexity and approximation (2009) Discrete Applied Mathematics, 157 (4), pp. 819-832
  • Demange, M., De Werra, D., Monnot, J., Paschos, V., Weighted node coloring: When stable sets are expensive (2002) Lecture Notes in Computer Science, 2573, pp. 114-125
  • De Ridder, H., Information System on Graph Classes and Their Inclusions (ISGCI), , http://www.graphclasses.org
  • Faenza, Y., Oriolo, G., Stauffer, G., An algorithmic decomposition of claw-free graphs leading to an O ( n 3) -algorithm for the weighted stable set problem (2011) Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 630-646. , D. Randall, San Francisco, CA
  • Finke, G., Jost, V., Queyranne, M., Sebö, A., Batch processing with interval graph compatibilities between tasks (2008) Discrete Applied Mathematics, 156 (5), pp. 556-568
  • Grötschel, M., Lovász, L., Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization (1981) Combinatorica, 1, pp. 169-197
  • Pemmaraju, S., Raman, R., Varadarajan, K., Buffer minimization using max-coloring (2004) Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 562-571. , J. Ian Munro, New Orleans, LA

Citas:

---------- APA ----------
Bonomo, F., Giandomenico, M. & Rossi, F. (2013) . A note on the Cornaz-Jost transformation to solve the graph coloring problem. Information Processing Letters, 113(18), 649-652.
http://dx.doi.org/10.1016/j.ipl.2013.05.014
---------- CHICAGO ----------
Bonomo, F., Giandomenico, M., Rossi, F. "A note on the Cornaz-Jost transformation to solve the graph coloring problem" . Information Processing Letters 113, no. 18 (2013) : 649-652.
http://dx.doi.org/10.1016/j.ipl.2013.05.014
---------- MLA ----------
Bonomo, F., Giandomenico, M., Rossi, F. "A note on the Cornaz-Jost transformation to solve the graph coloring problem" . Information Processing Letters, vol. 113, no. 18, 2013, pp. 649-652.
http://dx.doi.org/10.1016/j.ipl.2013.05.014
---------- VANCOUVER ----------
Bonomo, F., Giandomenico, M., Rossi, F. A note on the Cornaz-Jost transformation to solve the graph coloring problem. Inf. Process. Lett. 2013;113(18):649-652.
http://dx.doi.org/10.1016/j.ipl.2013.05.014