Navegar

Colección

Datos Estadísticas

Artículo

Méndez-Diaz, I.; Nasini, G.; Severín, D. "Polyhedral results for the equitable coloring problem" (2011) Electronic Notes in Discrete Mathematics. 37(C):159-164
La versión final de este artículo es de uso interno. El editor solo permite incluir en el repositorio el artículo en su versión post-print. Por favor, si usted la posee enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

In this work we study the polytope associated with a 0/1 integer programming formulation for the Equitable Coloring Problem. We find several families of valid inequalities and derive sufficient conditions in order to be facet-defining inequalities. We also present computational evidence of the effectiveness of including these inequalities as cuts in a Branch & Cut algorithm. © 2011 Elsevier B.V.

Registro:

Documento: Artículo
Título:Polyhedral results for the equitable coloring problem
Autor:Méndez-Diaz, I.; Nasini, G.; Severín, D.
Filiación:FCEyN, Universidad de Buenos Aires, Argentina
FCEIA, Universidad Nacional de Rosario, Argentina
Palabras clave:Branch & cut; Equitable graph coloring; Integer programming
Año:2011
Volumen:37
Número:C
Página de inicio:159
Página de fin:164
DOI: http://dx.doi.org/10.1016/j.endm.2011.05.028
Título revista:Electronic Notes in Discrete Mathematics
Título revista abreviado:Electron. Notes Discrete Math.
ISSN:15710653
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v37_nC_p159_MendezDiaz

Referencias:

  • Kubale, M., (2004) Graph Colorings, , AMS, Providence, Rhode Island
  • Meyer, W., Equitable Coloring (1973) Amer. Math. Monthly, 80, pp. 920-922
  • Campêlo, M., Corrêa, R., Campos, V., On the asymmetric representatives formulation for the vertex coloring problem (2008) Discrete Appl. Math., 156, pp. 1097-1111
  • Méndez-Díaz, I., Zabala, P., A cutting plane algorithm for graph coloring (2008) Discrete Appl. Math., 156, pp. 159-179
  • Bahiense, L., Frota, Y., Maculan, N., Noronha, T., Ribeiro, C., A branch-and-cut algorithm for equitable coloring based on a formulation by representatives (2009) Electr. Notes Discrete Math., 35, pp. 347-352
  • Méndez-Díaz, I., Nasini, G., Severin, D., A branch-and-cut algorithm for the equitable graph coloring problem, ALIO-INFORMS Joint International Meeting, Buenos Aires, Argentina, 2010

Citas:

---------- APA ----------
Méndez-Diaz, I., Nasini, G. & Severín, D. (2011) . Polyhedral results for the equitable coloring problem. Electronic Notes in Discrete Mathematics, 37(C), 159-164.
http://dx.doi.org/10.1016/j.endm.2011.05.028
---------- CHICAGO ----------
Méndez-Diaz, I., Nasini, G., Severín, D. "Polyhedral results for the equitable coloring problem" . Electronic Notes in Discrete Mathematics 37, no. C (2011) : 159-164.
http://dx.doi.org/10.1016/j.endm.2011.05.028
---------- MLA ----------
Méndez-Diaz, I., Nasini, G., Severín, D. "Polyhedral results for the equitable coloring problem" . Electronic Notes in Discrete Mathematics, vol. 37, no. C, 2011, pp. 159-164.
http://dx.doi.org/10.1016/j.endm.2011.05.028
---------- VANCOUVER ----------
Méndez-Diaz, I., Nasini, G., Severín, D. Polyhedral results for the equitable coloring problem. Electron. Notes Discrete Math. 2011;37(C):159-164.
http://dx.doi.org/10.1016/j.endm.2011.05.028