Artículo
Méndez Díaz, I.; Zabala, P. "A polyhedral approach for graph coloring" (2000) Electronic Notes in Discrete Mathematics. 7:178-181
Consulte la política de Acceso Abierto del editor
Abstract:
We present an approach based on an integer programming formulation of the graph coloring problem. Our goal is to develop a model that removes some symmetrical solutions obtained by color permutations. We study the problem from a polyhedral point of view and determine some families of facets of the associated polytope. The theoretical results described here will be used to design an efficient Branch&Cut algorithm in a future work.
Registro:
| Documento: | Artículo |
| Título: | A polyhedral approach for graph coloring |
| Autor: | Méndez Díaz, I.; Zabala, P. |
| Filiación: | Departamento de Computación, FCEyN, Universidad de Buenos Aires, Argentina |
| Palabras clave: | Facets of Polyhedra; Graph Coloring; Integer Programming |
| Año: | 2000 |
| Volumen: | 7 |
| Página de inicio: | 178 |
| Página de fin: | 181 |
| 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_v7_n_p178_MendezDiaz |
Referencias:
- Coll, P., Marenco, J., Méndez Díaz, I., Zabala, P., An Integer Programming Model for the Graph Coloring Problem (2000) Annals of X CLAIO, , Mexico
- Sewell, E.C., An improved algorithm for exact graph coloring (1996) DIMACS, , JOHNSON, D. and TRICK, M. eds
- Mehrotra, A., Trick, M., A column generation approach for graph coloring (1996) INFORMS J. on Computing, 8 (4), pp. 344-353
Citas:
---------- APA ----------
Méndez Díaz, I. & Zabala, P. (2000) . A polyhedral approach for graph coloring. Electronic Notes in Discrete Mathematics, 7, 178-181.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v7_n_p178_MendezDiaz [ ]
---------- CHICAGO ----------
Méndez Díaz, I., Zabala, P. "A polyhedral approach for graph coloring" . Electronic Notes in Discrete Mathematics 7 (2000) : 178-181.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v7_n_p178_MendezDiaz [ ]
---------- MLA ----------
Méndez Díaz, I., Zabala, P. "A polyhedral approach for graph coloring" . Electronic Notes in Discrete Mathematics, vol. 7, 2000, pp. 178-181.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v7_n_p178_MendezDiaz [ ]
---------- VANCOUVER ----------
Méndez Díaz, I., Zabala, P. A polyhedral approach for graph coloring. Electron. Notes Discrete Math. 2000;7:178-181.Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v7_n_p178_MendezDiaz [ ]
