Artículo
Méndez-Díaz, I.; Zabala, P. "A cutting plane algorithm for graph coloring" (2008) Discrete Applied Mathematics. 156(2):159-179
Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte la política de Acceso Abierto del editor
Abstract:
We present an approach based on integer programming formulations of the graph coloring problem. Our goal is to develop models that remove 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 0/1-polytope associated with one of these integer programming formulations. The theoretical results described here are used to design an efficient Cutting Plane algorithm. © 2007 Elsevier B.V. All rights reserved.
Registro:
| Documento: | Artículo |
| Título: | A cutting plane algorithm 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: | Cutting plane algorithms; Facets of polyhedra; Graph coloring; Integer programming; Computer programming; Graph theory; Integer programming; Problem solving; Cutting plane algorithms; Facets of polyhedra; Graph coloring; Algorithms |
| Año: | 2008 |
| Volumen: | 156 |
| Número: | 2 |
| Página de inicio: | 159 |
| Página de fin: | 179 |
| DOI: | http://dx.doi.org/10.1016/j.dam.2006.07.010 |
| 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_v156_n2_p159_MendezDiaz.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v156_n2_p159_MendezDiaz |
Referencias:
- Brélaz, D., New methods to color the vertices of a graph (1979) Comm. ACM, 22, pp. 251-256
- Grötschel, M., Lovász, L., Schrijver, A., (1988) Geometric Algorithms and Combinatorial Optimization, , Springer, Berlin
- Junger, M., Thienel, S., The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization (2000) Software Practice and Experience, 30 (11), pp. 1325-1352
- Karp, R., Reducibility among combinatorial problems (1972) Complexity of Computer Computations, pp. 85-104. , Miller R., and Thatcher J. (Eds)
- Kubale, M., Jackowski, B., A generalized implicit enumeration algorithm for graph coloring (1985) Comm. ACM, 28 (4), pp. 412-418
- Mehrotra, A., Trick, M., A column generation approach for graph coloring (1996) INFORMS J. Comput., 8 (4), pp. 344-353
- Nemhauser, G.L., Wolsey, L., (1988) Integer and Combinatorial Optimization, , Wiley, New York
- Padberg, M.W., On the facial structure of set packing polyhedral (1973) Math. Programming, 5, pp. 199-215
- Sager, T.J., Lin, S., A pruning procedure for exact graph coloring (1991) ORSA J. Comput., 3 (3), pp. 226-230
- Sewell, E.C., An improved algorithm for exact graph coloring (1996) DIMACS, , Johnson D., and Trick M. (Eds)
- Wolsey, L., (1998) Integer a Programming, , Wiley, New York
Citas:
---------- APA ----------
Méndez-Díaz, I. & Zabala, P. (2008) . A cutting plane algorithm for graph coloring. Discrete Applied Mathematics, 156(2), 159-179.http://dx.doi.org/10.1016/j.dam.2006.07.010
---------- CHICAGO ----------
Méndez-Díaz, I., Zabala, P. "A cutting plane algorithm for graph coloring" . Discrete Applied Mathematics 156, no. 2 (2008) : 159-179.http://dx.doi.org/10.1016/j.dam.2006.07.010
---------- MLA ----------
Méndez-Díaz, I., Zabala, P. "A cutting plane algorithm for graph coloring" . Discrete Applied Mathematics, vol. 156, no. 2, 2008, pp. 159-179.http://dx.doi.org/10.1016/j.dam.2006.07.010
---------- VANCOUVER ----------
Méndez-Díaz, I., Zabala, P. A cutting plane algorithm for graph coloring. Discrete Appl Math. 2008;156(2):159-179.http://dx.doi.org/10.1016/j.dam.2006.07.010
