Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

In the b-coloring problem, we aim to assign colors from a set C to the vertices of a graph G in such a way that adjacent vertices do not receive the same color, and for every c∈C we have a c-colored vertex v in G such that every color in C∖{c} is assigned to at least one of v's neighbors. It has been shown that b-coloring is NP-complete, so we propose in this article an approach for the problem under integer programming techniques. To this end, we give an integer programming formulation and study the associated polytope. We provide several families of valid inequalities, and analyze facetness conditions for them. Finally, we show computational evidence suggesting that the given inequalities may be useful in a branch-and-cut environment. © 2018 Elsevier B.V.

Registro:

Documento: Artículo
Título:An integer programming approach to b-coloring
Autor:Koch, I.; Marenco, J.
Filiación:Instituto de Industria, Universidad Nacional de General Sarmiento, Buenos Aires, Argentina
Instituto de Ciencias, Universidad Nacional de General Sarmiento, Argentina
Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
Palabras clave:b-coloring; Cutting planes; Facets; Integer programming; Color; Graph theory; Adjacent vertices; Branch and cut; Coloring problems; Cutting planes; Facets; Integer programming formulations; NP Complete; Valid inequality; Integer programming
Año:2018
DOI: http://dx.doi.org/10.1016/j.disopt.2018.12.001
Título revista:Discrete Optimization
Título revista abreviado:Discrete Optim.
ISSN:15725286
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15725286_v_n_p_Koch

Referencias:

  • Irving, R.W., Manlove, D.F., The b-chromatic number of a graph (1999) Discrete Appl. Math., 91, pp. 127-141
  • Jakovac, M., Peterin, I., The b-chromatic number and related topics-a survey (2018) Discrete Appl. Math., 235, pp. 184-201
  • Dekar, L., Kheddouci, H., A graph b-coloring based scheme for Composition-Oriented Web Services Abstraction: COWSA (2008), pp. 77-82. , PhD Symposium of the 6th International Conference on Service Oriented Computing, ICSOC‘2008, France; Elghazel, H., Deslandres, V., Hacid, M., Dussauchoy, A., Kheddouci, H., (2006) A New Clustering Approach for Symbolic Data and Its Validation: Application to the Healthcare Data, Lecture Notes Artificial Intelligence, 4203, pp. 473-482
  • Gaceb, D., Eglin, V., Lebourgeois, F., Emptoz, H., Improvement of postal mail sorting system (2008) Int. J. Document Analysis Recogn., 11 (2), pp. 67-80
  • Gaceb, D., Eglin, V., Lebourgeois, F., Emptoz, H., Robust approach of address block localization in business mail by graph coloring (2009) Int. Arab J. Inform.Tech., 2 (3), pp. 221-229
  • Kratochvíl, J., Tuza, Z., Voigt, M., On the b-chromatic number of a graph (2002) Lecture Notes in Comput. Sci., 2573, pp. 310-320
  • Havet, F., Linhares-Sales, C., Sampaio, L., b-coloring of tight graphs (2012) Discrete Appl. Math., 160 (18), pp. 2709-2715
  • Lima, C.V.G.C., Martins, N.A., Sampaio, L., Santos, M.C., Silva, A., b-chromatic index of graphs (2013) Electron. Notes Discrete Math., 44, pp. 9-14
  • Barth, D., Cohen, J., Faik, T., On the b-continuity property of graphs (2007) Discrete Appl. Math., 155 (13), pp. 1761-1768
  • Fister, I., Peterin, I., Mernik, M., Črepišek, M., Hybrid evolutionary algorithm for the b-chromatic number (2015) J. Heuristics, 21 (4), pp. 501-521
  • Koch, I., Peterin, I., The b-chromatic index of direct product of graphs (2015) Discrete Appl. Math., 190-191, pp. 109-117
  • Coll, P., Marenco, J., Méndez-Díaz, I., Zabala, Facets of the graph coloring polytope (2002) Ann. Oper. Res., 116 (1-4), pp. 79-90
  • Méndez-Díaz, I., Zabala, P., A branch-and-cut algorithm for graph coloring (2006) Discrete Appl. Math., 154 (5), pp. 826-847
  • Méndez-Díaz, I., Zabala, P., A cutting plane algorithm for graph coloring (2008) Discrete Appl. Math., 156 (2), pp. 159-179
  • Campêlo, M., Campos, V., Corrêa, R., On the asymmetric representatives formulation for the vertex coloring problem (2008) Discrete Appl. Math., 156 (7), pp. 1097-1111
  • Campêlo, M., Corrêa, R., Frota, Y., Cliques, holes and the vertex coloring polytope (2004) Inf. Process. Lett., 89 (4), pp. 159-164
  • Borndörfer, R., Eisenblätter, A., Grötschel, M., Martin, A., The orientation model for frequency assignment problems (1998), pp. 98-101. , ZIB-Berlin; Burke, E., Marecek, J., Parkes, A., Rudová, H., A supernodal formulation of vertex colouring with applications in course timetabling (2010) Ann. Oper. Res., 179 (1), pp. 105-130
  • Hansen, P., Labbé, M., Schindl, D., Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results (2009) Discrete Optim., 6 (2), pp. 135-147
  • Held, S., Cook, W., Sewell, E., Safe lower bounds for graph coloring (2011) IPCO, Lecture Notes in Computer Science, 6655, pp. 261-273. , Springer
  • Malaguti, E., Monaci, M., Toth, P., An exact approach for the vertex coloring problem (2011) Discrete Optim., 8 (2), pp. 174-190
  • Mehrotra, A., Trick, M., A column generation approach for graph coloring (1996) INFORMS J. Comput., 8 (4), pp. 344-354
  • Gualandi, S., Malucelli, F., Exact solution of graph coloring problems via constraint programming and column generation (2012) INFORMS J. Comput., 24 (1), pp. 81-100
  • Shimizu, S., Yamaguchi, K., Saitoh, T., Masuda, S., A fast heuristic for the minimum weight vertex cover problem (2016) ICIS, pp. 1-5. , IEEE Computer Society

Citas:

---------- APA ----------
Koch, I. & Marenco, J. (2018) . An integer programming approach to b-coloring. Discrete Optimization.
http://dx.doi.org/10.1016/j.disopt.2018.12.001
---------- CHICAGO ----------
Koch, I., Marenco, J. "An integer programming approach to b-coloring" . Discrete Optimization (2018).
http://dx.doi.org/10.1016/j.disopt.2018.12.001
---------- MLA ----------
Koch, I., Marenco, J. "An integer programming approach to b-coloring" . Discrete Optimization, 2018.
http://dx.doi.org/10.1016/j.disopt.2018.12.001
---------- VANCOUVER ----------
Koch, I., Marenco, J. An integer programming approach to b-coloring. Discrete Optim. 2018.
http://dx.doi.org/10.1016/j.disopt.2018.12.001