Artículo

Méndez-Díaz, I.; Zabala, P. "A Branch-and-Cut algorithm for graph coloring" (2006) Discrete Applied Mathematics. 154(5 SPEC ISS):826-847
Artículo de Acceso Abierto. Puede ser descargado en su versión final
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Registro:

Documento: Artículo
Título:A Branch-and-Cut 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:Branch-and-Cut algorithms; Graph coloring; Integer programming; Graph theory; Integer programming; Mathematical models; Branch-and-cut algorithms; Graph coloring; Algorithms
Año:2006
Volumen:154
Número:5 SPEC ISS
Página de inicio:826
Página de fin:847
DOI: http://dx.doi.org/10.1016/j.dam.2005.05.022
Handle:http://hdl.handle.net/20.500.12110/paper_0166218X_v154_n5SPECISS_p826_MendezDiaz
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_v154_n5SPECISS_p826_MendezDiaz.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v154_n5SPECISS_p826_MendezDiaz

Referencias:

  • 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 (11). , Maastricht University
  • Applegate, D., Bixby, R., Chvátal, V., Cook, W., On the solution of traveling salesman problems (1998) Documenta Mathematica Journal der Deutschen Mathematiker-vereinigung, pp. 645-656. , International Congress of Mathematicians
  • Balas, E., Ceria, S., Cornuéjols, G., Pataki, G.G., Polyhedral methods for the maximum clique problem (1996) Cliques, Coloring, and Satisfiability, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, 26, pp. 11-27. , D. Johnson M. Trick
  • Barahona, F., Ladányi, L., Branch-and-Cut Based on the volume algorithm: Steiner trees in graphs and max cut (2001) IBM Research Report, RC22221
  • Blasum, U., Hochstättler, W., Application of the Branch and Cut method to the vehicle routing problem (2000) Zentrum für Angewandte Informatik Köln Technical Report, ZPR2000-386
  • Brélatz, D., New methods to color the vertices of a graph (1979) Comm. ACM, 22, pp. 251-256
  • Coll, P., Marenco, J., Méndez-Díaz, I., Zabala, P., Facets of the graph coloring polytope (2002) Ann. Oper. Res., 116, pp. 79-90
  • (1997) CPLEX Linear Optimization 6.0 with Mixed Integer & Barrier Solvers, , ILOG
  • Chaitin, G.J., Auslander, M., Chandra, A.K., Cocke, J., Hopkins, M.E., Markstein, P., Register allocation via coloring (1981) Computer Languages, 6, pp. 47-57
  • Culberson, J., Graph Coloring Bibliography, , http://web.cs.ualberta.ca/
  • De Werra, D., Heuristics for graph coloring (1990) Computing, 7, pp. 191-208
  • DIMACS Instances, , http://mat.gsia.cmu.edu/COLOR02
  • Glover, F., Parker, M., Ryan, J., Coloring by tabu branch and bound (1996) Coloring Cliques Coloring and Satisfiability, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, 26, pp. 285-308. , D. Johnson M. Trick
  • Herz, A., De Werra, D., Using tabu search techniques for graph coloring (1987) Computing, 39, pp. 345-351
  • Jensen, T., Toft, B., Graph coloring problems (1995) Series in Discrete Mathematics and Optimization, , Wiley-Interscience Wiley, New York
  • Cliques, coloring, and satisfiability (1996) DIMACS Series on Discrete Mathematics and Theoretical Computer Science, 26. , D. Johnson, M. Trick (Eds.)
  • 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. , R. Miller J. Thatcher
  • Koster, A., (1999) Frequency Assignment, Models and Algorithms, , Ph.D. Thesis, Universiteit Maastricht
  • Kubale, M., Jackowski, B., A generalized implicit enumeration algorithm for graph coloring (1985) Commun. ACM, 28 (4), pp. 412-418
  • Leighton, F.T., A graph coloring algorithm for large scheduling problems (1979) J. Res. Natl. Bur. Standards, 84, pp. 489-506
  • Mannino, C., Sassano, A., An exact algorithm for the maximum stable set problem (1994) Comput. Optimization and Applications, 3, pp. 243-258
  • McHugh, J., (1990) Algorithmic Graph Theory, , Prentice-Hall Englewood Cliffs, NJ
  • Mehrotra, A., Trick, M., A column generation approach for graph coloring (1996) INFORMS J. Comput., 8 (4), pp. 344-353
  • Méndez-Díaz, I., (2003) Problema de Coloreo de Grafos-un Estudio Poliedral y un Algoritmo Branch-and-cut, , Tesis Doctoral, Universidad de Buenos Aires, Argentina
  • Méndez-Díaz, I., Zabala, P., A polyhedral approach for graph coloring (2001) Electronics Notes in Discrete Mathematics, 7
  • Méndez-Díaz, I., Zabala, P., (2002) Polyhedral Results for Graph Coloring, , TR 02-001 Departamento de Computación, Universidad de Buenos Aires
  • Nemhauser, G., Sigismondi, G., A strong cutting plane/branch-and-bound algorithm for node packing (1992) J. Oper. Res. Soc., 43 (5), pp. 443-457
  • Nemhauser, G., Wolsey, L., (1988) Integer and Combinatorial Optimization, , Wiley New York
  • Padberg, M.W., On the facial structure of set packing polyhedral (1973) Math. Prog., 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
  • Sassano, A., On the facial structure of the set covering polytope (1989) Math. Prog., 44, pp. 181-202
  • Sewell, E., An improved algorithm for exact graph coloring (1996) DIMACS Series on Discrete Mathematics and Theoretical Computer Science, 26, pp. 359-373. , D. Johnson M. Trick
  • Wolsey, L., (1998) Integer Programming, , Wiley New York

Citas:

---------- APA ----------
Méndez-Díaz, I. & Zabala, P. (2006) . A Branch-and-Cut algorithm for graph coloring. Discrete Applied Mathematics, 154(5 SPEC ISS), 826-847.
http://dx.doi.org/10.1016/j.dam.2005.05.022
---------- CHICAGO ----------
Méndez-Díaz, I., Zabala, P. "A Branch-and-Cut algorithm for graph coloring" . Discrete Applied Mathematics 154, no. 5 SPEC ISS (2006) : 826-847.
http://dx.doi.org/10.1016/j.dam.2005.05.022
---------- MLA ----------
Méndez-Díaz, I., Zabala, P. "A Branch-and-Cut algorithm for graph coloring" . Discrete Applied Mathematics, vol. 154, no. 5 SPEC ISS, 2006, pp. 826-847.
http://dx.doi.org/10.1016/j.dam.2005.05.022
---------- VANCOUVER ----------
Méndez-Díaz, I., Zabala, P. A Branch-and-Cut algorithm for graph coloring. Discrete Appl Math. 2006;154(5 SPEC ISS):826-847.
http://dx.doi.org/10.1016/j.dam.2005.05.022