Polyhedral results for the equitable coloring problem
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 effec...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | , |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
2011
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 03010caa a22004337a 4500 | ||
|---|---|---|---|
| 001 | PAPER-10422 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518204027.0 | ||
| 008 | 190411s2011 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-80053082107 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Méndez-Diaz, I. | |
| 245 | 1 | 0 | |a Polyhedral results for the equitable coloring problem |
| 260 | |c 2011 | ||
| 270 | 1 | 0 | |m Méndez-Diaz, I.; FCEyN, Universidad de Buenos AiresArgentina; email: imendez@dc.uba.ar |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Kubale, M., (2004) Graph Colorings, , AMS, Providence, Rhode Island | ||
| 504 | |a Meyer, W., Equitable Coloring (1973) Amer. Math. Monthly, 80, pp. 920-922 | ||
| 504 | |a 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 | ||
| 504 | |a Méndez-Díaz, I., Zabala, P., A cutting plane algorithm for graph coloring (2008) Discrete Appl. Math., 156, pp. 159-179 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 520 | 3 | |a 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. |l eng | |
| 593 | |a FCEyN, Universidad de Buenos Aires, Argentina | ||
| 593 | |a FCEIA, Universidad Nacional de Rosario, Argentina | ||
| 690 | 1 | 0 | |a BRANCH & CUT |
| 690 | 1 | 0 | |a EQUITABLE GRAPH COLORING |
| 690 | 1 | 0 | |a INTEGER PROGRAMMING |
| 700 | 1 | |a Nasini, G. | |
| 700 | 1 | |a Severín, D. | |
| 773 | 0 | |d 2011 |g v. 37 |h pp. 159-164 |k n. C |p Electron. Notes Discrete Math. |x 15710653 |t Electronic Notes in Discrete Mathematics | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-80053082107&doi=10.1016%2fj.endm.2011.05.028&partnerID=40&md5=75e775d790137cc2a94060ac2828a872 |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1016/j.endm.2011.05.028 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_15710653_v37_nC_p159_MendezDiaz |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v37_nC_p159_MendezDiaz |y Registro en la Biblioteca Digital |
| 961 | |a paper_15710653_v37_nC_p159_MendezDiaz |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 963 | |a VARI | ||
| 999 | |c 71375 | ||