A polyhedral approach for graph coloring
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 a...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
2000
|
| Acceso en línea: | Registro en Scopus Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 02375caa a22003617a 4500 | ||
|---|---|---|---|
| 001 | PAPER-2181 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518203134.0 | ||
| 008 | 190411s2000 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-33644608965 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Méndez Díaz, I. | |
| 245 | 1 | 2 | |a A polyhedral approach for graph coloring |
| 260 | |c 2000 | ||
| 270 | 1 | 0 | |m Departamento de Computación, FCEyN, Universidad de Buenos AiresArgentina; email: imendez@dc.uba.ar |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a 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 | ||
| 504 | |a Sewell, E.C., An improved algorithm for exact graph coloring (1996) DIMACS, , JOHNSON, D. and TRICK, M. eds | ||
| 504 | |a Mehrotra, A., Trick, M., A column generation approach for graph coloring (1996) INFORMS J. on Computing, 8 (4), pp. 344-353 | ||
| 520 | 3 | |a 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. |l eng | |
| 593 | |a Departamento de Computación, FCEyN, Universidad de Buenos Aires, Argentina | ||
| 690 | 1 | 0 | |a FACETS OF POLYHEDRA |
| 690 | 1 | 0 | |a GRAPH COLORING |
| 690 | 1 | 0 | |a INTEGER PROGRAMMING |
| 700 | 1 | |a Zabala, P. | |
| 773 | 0 | |d 2000 |g v. 7 |h pp. 178-181 |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-33644608965&partnerID=40&md5=4ff77d54e8d68251d3883701010d507f |y Registro en Scopus |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_15710653_v7_n_p178_MendezDiaz |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v7_n_p178_MendezDiaz |y Registro en la Biblioteca Digital |
| 961 | |a paper_15710653_v7_n_p178_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 63134 | ||