Facets of the graph coloring polytope

Mostrar otras versiones (1)

In this paper we present a study of the polytope associated to a classic linear integer programming formulation of the graph coloring problem. We determine some families of facets. This is the initial step for the development of a branch-and-cut algorithm to solve large instances of the graph colori...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Coll, P.
Otros Autores: Marenco, J., Méndez Díaz, I., Zabala, P.
Formato: Capítulo de libro
Lenguaje:Inglés
Publicado: 2002
Acceso en línea:Registro en Scopus
DOI
Handle
Registro en la Biblioteca Digital
Aporte de:Registro referencial: Solicitar el recurso aquí
Biblioteca Central Dr. Luis F. Leloir (FCEN) de Universidad de Buenos Aires
LEADER 05660caa a22006377a 4500
001 PAPER-5102
003 AR-BaUEN
005 20230518203443.0
008 190411s2002 xx ||||fo|||| 00| 0 eng|d
024 7 |2 scopus  |a 2-s2.0-0036449043 
040 |a Scopus  |b spa  |c AR-BaUEN  |d AR-BaUEN 
100 1 |a Coll, P. 
245 1 0 |a Facets of the graph coloring polytope 
260 |c 2002 
270 1 0 |m Coll, P.; Departamento de Computación, Fac. de Ciencias Exactas y Naturales, Universidad de Buenos Aires, C1428BGA-Buenos Aires, Argentina; email: pecoll@dc.uba.ar 
506 |2 openaire  |e Política editorial 
504 |a Aardal, K., Hipolito, A., Van Hoesel, C., Jansen, B., Roos, C., Terlaky, T., A branch-and-cut algorithm for the frequency assignment problem (1996) Research Memorandum 96/011, , Maastricht University 
504 |a Balas, E., Ceria, S., Cornuéjols, G., Pataki, G., Polyhedral methods for the maximum clique problem (1996) Cliques Coloring, and Satisfiability, 26, pp. 11-27. , DIMACS Series on Discrete Mathematics and Theoretical Computer Science. D. Johnson and M. Trick 
504 |a Brélaz, D., New methods to color the vertices of a graph (1979) Communications of the ACM, 22, pp. 251-256 
504 |a Christof, T., Loebel, A., Stoer, M., (1997) PORTA - A Polyhedron Representation Transformation Algorithm, Version 1.3 
504 |a De Werra, D., Heuristics for graph coloring (1990) Computing, (SUPPL. 7), pp. 191-208 
504 |a Glover, F., Parker, M., Ryan, J., Coloring by tabu branch and bound (1996) Cliques, Coloring, and Satisfiability, 26, pp. 285-308. , DIMACS Series on Discrete Mathematics and Theoretical Computer Science. D. Johnson and M. Trick 
504 |a Grotschel, M., Lovasz, L., Schrijver, A., (1988) Geometric Algorithms and Combinatorial Optimization, , Springer Berlin 
504 |a Herz, A., De Werra, D., Using tabu search techniques for graph coloring (1987) Computing, 39, pp. 345-351 
504 |a Johnson, D., The NP-completeness column: An ongoing guide (1985) Journal of Algorithms, 6, pp. 434-451 
504 |a Johnson, D., Trick, M., (1996) Cliques, Coloring, and Satisfiability, 26. , DIMACS Series on Discrete Mathematics and Theoretical Computer Science 
504 |a Karp, R., Reducibility among combinatorial problems (1972) Complexity of Computer Computations, pp. 85-104. , eds. R. Miller and J. Thatcher 
504 |a Kubale, M., Jackowski, B., A generalized implicit enumeration algorithm for graph coloring (1985) Communications of the ACM, 28 (4), pp. 412-418 
504 |a Mannino, C., Sassano, A., An exact algorithm for the maximum estable set problem (1994) Computational Optimization and Applications, 3, pp. 243-258 
504 |a Mehrotra, A., Trick, M., A column generation approach for graph coloring (1996) INFORMS Journal on Computing, 8 (4), pp. 344-353 
504 |a Nemhauser, G., Sigismondi, G., A strong cutting plane/branch-and-bound algorithm for node packing (1992) Journal of Operations Research Society, 43 (5), pp. 443-457 
504 |a Nemhauser, G., Wolsey, L., (1988) Integer and Combinatorial Optimization, , Wiley New York 
504 |a Padberg, M.W., On the facial structure of set packing polyhedral (1973) Mathematical Programming, 5, pp. 199-215 
504 |a Sager, T.J., Lin, S., A pruning procedure for exact graph coloring (1991) ORSA Journal on Computing, 3 (3), pp. 226-230 
504 |a Sassano, A., On the facial structure of the Set Covering Polytope (1989) Mathematical Programming, 44, pp. 181-202 
504 |a Sewell, E., An improved algorithm for exact graph coloring (1996) Cliques Coloring, and Satisfiability, 26, pp. 359-373. , DIMACS Series on Discrete Mathematics and Theoretical Computer Science. Johnson and M. Trick 
504 |a Wolsey, L., (1998) Integer Programming, , Wiley New York 
520 3 |a In this paper we present a study of the polytope associated to a classic linear integer programming formulation of the graph coloring problem. We determine some families of facets. This is the initial step for the development of a branch-and-cut algorithm to solve large instances of the graph coloring problem.  |l eng 
536 |a Detalles de la financiación: Secretaría de Ciencia y Técnica, Universidad de Buenos Aires, TW82 
536 |a Detalles de la financiación: Consejo Nacional de Investigaciones Científicas y Técnicas, 644/98 
536 |a Detalles de la financiación: ∗This research was partially supported by UBACYT Grant TW82 and PID CONICET Grant 644/98. 
593 |a Departamento de Computación, Fac. de Ciencias Exactas y Naturales, Universidad de Buenos Aires, C1428BGA-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 Marenco, J. 
700 1 |a Méndez Díaz, I. 
700 1 |a Zabala, P. 
773 0 |d 2002  |g v. 116  |h pp. 79-90  |k n. 1-4  |p Ann. Oper. Res.  |x 02545330  |t Annals of Operations Research 
856 4 1 |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-0036449043&doi=10.1023%2fA%3a1021315911306&partnerID=40&md5=2b83bf4a603d3b52e31c9f06b1d4e96f  |y Registro en Scopus 
856 4 0 |u https://doi.org/10.1023/A:1021315911306  |y DOI 
856 4 0 |u https://hdl.handle.net/20.500.12110/paper_02545330_v116_n1-4_p79_Coll  |y Handle 
856 4 0 |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_02545330_v116_n1-4_p79_Coll  |y Registro en la Biblioteca Digital 
961 |a paper_02545330_v116_n1-4_p79_Coll  |b paper  |c PE 
962 |a info:eu-repo/semantics/article  |a info:ar-repo/semantics/artículo  |b info:eu-repo/semantics/publishedVersion 
999 |c 66055 

Ejemplares similares