An integer programming approach to b-coloring
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 ha...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
Elsevier B.V.
2018
|
| Materias: | |
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 07146caa a22007817a 4500 | ||
|---|---|---|---|
| 001 | PAPER-25336 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518205722.0 | ||
| 008 | 190410s2018 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-85058492736 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Koch, I. | |
| 245 | 1 | 3 | |a An integer programming approach to b-coloring |
| 260 | |b Elsevier B.V. |c 2018 | ||
| 270 | 1 | 0 | |m Marenco, J.; Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos AiresArgentina; email: jmarenco@dc.uba.ar |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Irving, R.W., Manlove, D.F., The b-chromatic number of a graph (1999) Discrete Appl. Math., 91, pp. 127-141 | ||
| 504 | |a Jakovac, M., Peterin, I., The b-chromatic number and related topics-a survey (2018) Discrete Appl. Math., 235, pp. 184-201 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a Havet, F., Linhares-Sales, C., Sampaio, L., b-coloring of tight graphs (2012) Discrete Appl. Math., 160 (18), pp. 2709-2715 | ||
| 504 | |a 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 | ||
| 504 | |a Barth, D., Cohen, J., Faik, T., On the b-continuity property of graphs (2007) Discrete Appl. Math., 155 (13), pp. 1761-1768 | ||
| 504 | |a 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 | ||
| 504 | |a Koch, I., Peterin, I., The b-chromatic index of direct product of graphs (2015) Discrete Appl. Math., 190-191, pp. 109-117 | ||
| 504 | |a 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 | ||
| 504 | |a Méndez-Díaz, I., Zabala, P., A branch-and-cut algorithm for graph coloring (2006) Discrete Appl. Math., 154 (5), pp. 826-847 | ||
| 504 | |a Méndez-Díaz, I., Zabala, P., A cutting plane algorithm for graph coloring (2008) Discrete Appl. Math., 156 (2), pp. 159-179 | ||
| 504 | |a 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 | ||
| 504 | |a Campêlo, M., Corrêa, R., Frota, Y., Cliques, holes and the vertex coloring polytope (2004) Inf. Process. Lett., 89 (4), pp. 159-164 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a Held, S., Cook, W., Sewell, E., Safe lower bounds for graph coloring (2011) IPCO, Lecture Notes in Computer Science, 6655, pp. 261-273. , Springer | ||
| 504 | |a Malaguti, E., Monaci, M., Toth, P., An exact approach for the vertex coloring problem (2011) Discrete Optim., 8 (2), pp. 174-190 | ||
| 504 | |a Mehrotra, A., Trick, M., A column generation approach for graph coloring (1996) INFORMS J. Comput., 8 (4), pp. 344-354 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 520 | 3 | |a 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. |l eng | |
| 536 | |a Article in Press | ||
| 593 | |a Instituto de Industria, Universidad Nacional de General Sarmiento, Buenos Aires, Argentina | ||
| 593 | |a Instituto de Ciencias, Universidad Nacional de General Sarmiento, Argentina | ||
| 593 | |a Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina | ||
| 690 | 1 | 0 | |a B-COLORING |
| 690 | 1 | 0 | |a CUTTING PLANES |
| 690 | 1 | 0 | |a FACETS |
| 690 | 1 | 0 | |a INTEGER PROGRAMMING |
| 690 | 1 | 0 | |a GRAPH THEORY |
| 690 | 1 | 0 | |a ADJACENT VERTICES |
| 690 | 1 | 0 | |a BRANCH AND CUT |
| 690 | 1 | 0 | |a COLORING PROBLEMS |
| 690 | 1 | 0 | |a CUTTING PLANES |
| 690 | 1 | 0 | |a FACETS |
| 690 | 1 | 0 | |a INTEGER PROGRAMMING FORMULATIONS |
| 690 | 1 | 0 | |a NP COMPLETE |
| 690 | 1 | 0 | |a VALID INEQUALITY |
| 690 | 1 | 0 | |a INTEGER PROGRAMMING |
| 650 | 1 | 7 | |2 spines |a COLOR |
| 700 | 1 | |a Marenco, J. | |
| 773 | 0 | |d Elsevier B.V., 2018 |p Discrete Optim. |x 15725286 |t Discrete Optimization | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-85058492736&doi=10.1016%2fj.disopt.2018.12.001&partnerID=40&md5=93a1f840d270b23d13ea7fd30ab79e30 |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1016/j.disopt.2018.12.001 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_15725286_v_n_p_Koch |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15725286_v_n_p_Koch |y Registro en la Biblioteca Digital |
| 961 | |a paper_15725286_v_n_p_Koch |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 86289 | ||