A branch-and-price algorithm for the (k,c)-coloring problem
In this article, we study the (k,c)-coloring problem, a generalization of the vertex coloring problem where we have to assign k colors to each vertex of an undirected graph, and two adjacent vertices can share at most c colors. We propose a new formulation for the (k,c)-coloring problem and develop...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | , , |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
Wiley-Liss Inc.
2015
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 06605caa a22008297a 4500 | ||
|---|---|---|---|
| 001 | PAPER-13909 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518204421.0 | ||
| 008 | 190411s2015 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-84930518623 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Malaguti, E. | |
| 245 | 1 | 2 | |a A branch-and-price algorithm for the (k,c)-coloring problem |
| 260 | |b Wiley-Liss Inc. |c 2015 | ||
| 270 | 1 | 0 | |m Malaguti, E.; DEI, University of Bologna, Viale Risorgimento 2, Italy |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Aardal, K., Van Hoesel, S., Koster, A., Mannino, C., Sassano, A., Models and solution techniques for the frequency assignment problem (2003) 4OR, 1, pp. 261-317 | ||
| 504 | |a Farley, A.A., A note on bounding a class of linear programming problems, including cutting stock problems (1990) Oper Res, 38, pp. 922-923 | ||
| 504 | |a Furini, F., Malaguti, E., Exact weighted vertex coloring via branch-and-price (2012) Discrete Optim, 9, pp. 130-136 | ||
| 504 | |a Garey, M., Johnson, D., Computers and intractability: A guide to the theory of NP-completeness (1979) DIMACS Series in Discrete Mathematics and Theoretical Computer Science, , Freeman, New York | ||
| 504 | |a Gualandi, S., Malucelli, F., Exact solution of graph coloring problems via constraint programming and column generation (2012) INFORMS J Comput, 24, pp. 81-100 | ||
| 504 | |a Halldõrsson, M., Kortsarz, G., Multicoloring: Problems and techniques, mathematical foundations of computer science 2004 (2004) Lect Notes Comput Sci, 3153, pp. 25-41 | ||
| 504 | |a Held, S., Cook, W., Sewell, E., Maximum-weight stable sets and safe lower bounds for graph coloring (2012) Math Program Comput, 4, pp. 363-381 | ||
| 504 | |a Hoshino, E., Frota, Y., De Souza, C.C., A branch-and-price approach for the partition coloring problem (2011) Oper Res Lett, 39, pp. 132-137 | ||
| 504 | |a Konc, J., Janezic, D., An improved branch and bound algorithm for the maximum clique problem (2007) MATCH Commun Math Comput Chem, 58, pp. 569-590 | ||
| 504 | |a Koster, A., Tieves, M., Column generation for frequency assignment in slow frequency hopping networks (2012) EURASIP J Wireless Commun Networking, 253, pp. 1-14 | ||
| 504 | |a Koster, A., Zymolka, A., Tight LP-based lower bounds for wavelength conversion in optical networks (2007) Stat Neerl, 61, pp. 115-136 | ||
| 504 | |a Malaguti, E., The vertex coloring problem and its generalizations (2009) 4OR Q J Oper Res, 7, pp. 101-104 | ||
| 504 | |a Malaguti, E., Méndez-Díaz, I., Miranda-Bront, J., Zabala, P., Coloring via column generation (2013) Electron Notes Discrete Math, 41, pp. 447-454 | ||
| 504 | |a Malaguti, E., Monaci, M., Toth, P., An exact approach for the vertex coloring problem (2011) Discrete Optim, 8, pp. 174-190 | ||
| 504 | |a Malaguti, E., Toth, P., A survey on vertex coloring problems (2010) Int Trans Oper Res, 17, pp. 1-34 | ||
| 504 | |a Mehrotra, A., Trick, M., A column generation approach for graph coloring (1996) INFORMS J Comput, 8, pp. 344-354 | ||
| 504 | |a Mehrotra, A., Trick, M., A branch-and-price approach for graph multicoloring (2007) Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies, Operations Research/Computer Science Interfaces Series, 37, pp. 15-29. , E. Baker, A. Joseph, A. Mehrotra, and M. Trick (Editors), Springer | ||
| 504 | |a Méndez-Díaz, I., Zabala, P., A branch-and-cut algorithm for graph coloring (2006) Discrete Appl Math, 154, pp. 826-847 | ||
| 504 | |a Méndez-Díaz, I., Zabala, P., A cuttting plane algorithm for graph coloring (2008) Discrete Appl Math, 156, pp. 159-179 | ||
| 504 | |a Méndez-Díaz, I., Zabala, P., The (k, k - 1) coloring problem (2008) Proc Int Symp Comb Optim, , Warwick, UK | ||
| 504 | |a Méndez-Díaz, I., Zabala, P., Solving a multicoloring problem with overlaps using integer programming (2010) Discrete Appl Math, 158, pp. 349-354 | ||
| 504 | |a Zymolka, A., (2006) Design of Survivable Optical Networks by Mathematical Optimization, Ph.D. Thesis, , TU Berlin | ||
| 520 | 3 | |a In this article, we study the (k,c)-coloring problem, a generalization of the vertex coloring problem where we have to assign k colors to each vertex of an undirected graph, and two adjacent vertices can share at most c colors. We propose a new formulation for the (k,c)-coloring problem and develop a Branch-and-Price algorithm. We tested the algorithm on instances having from 20 to 80 vertices and different combinations for k and c, and compare it with a recent algorithm proposed in the literature. Computational results show that the overall approach is effective and has very good performance on instances where the previous algorithm fails. © 2014 Wiley Periodicals, Inc. NETWORKS, 2014 Vol. 65(4), 353-366 2015 © 2014 Wiley Periodicals, Inc. |l eng | |
| 593 | |a DEI, University of Bologna, Viale Risorgimento 2, Bologna, 40136, Italy | ||
| 593 | |a Department of Computer Science, FCEyN, University of Buenos Aires, Buenos Aires, Argentina | ||
| 593 | |a Consejo Nacional de Investigaciones Científicas y Técnicas, Argentina | ||
| 690 | 1 | 0 | |a BRANCH-AND-PRICE |
| 690 | 1 | 0 | |a COLUMN GENERATION |
| 690 | 1 | 0 | |a COMPUTATIONAL EXPERIMENTS |
| 690 | 1 | 0 | |a FREQUENCY ASSIGNMENT |
| 690 | 1 | 0 | |a HEURISTICS |
| 690 | 1 | 0 | |a MULTICOLORING |
| 690 | 1 | 0 | |a VERTEX COLORING |
| 690 | 1 | 0 | |a COLORING |
| 690 | 1 | 0 | |a COSTS |
| 690 | 1 | 0 | |a INTEGER PROGRAMMING |
| 690 | 1 | 0 | |a LINEAR PROGRAMMING |
| 690 | 1 | 0 | |a BRANCH AND PRICE |
| 690 | 1 | 0 | |a COLUMN GENERATION |
| 690 | 1 | 0 | |a COMPUTATIONAL EXPERIMENT |
| 690 | 1 | 0 | |a FREQUENCY ASSIGNMENTS |
| 690 | 1 | 0 | |a HEURISTICS |
| 690 | 1 | 0 | |a MULTICOLORING |
| 690 | 1 | 0 | |a VERTEX COLORING |
| 690 | 1 | 0 | |a ALGORITHMS |
| 700 | 1 | |a Méndez-Díaz, I. | |
| 700 | 1 | |a José Miranda-Bront, J. | |
| 700 | 1 | |a Zabala, P. | |
| 773 | 0 | |d Wiley-Liss Inc., 2015 |g v. 65 |h pp. 353-366 |k n. 4 |p Networks |x 00283045 |t Networks | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-84930518623&doi=10.1002%2fnet.21579&partnerID=40&md5=107d0000e93939267cef5b3c09ab9a43 |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1002/net.21579 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_00283045_v65_n4_p353_Malaguti |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00283045_v65_n4_p353_Malaguti |y Registro en la Biblioteca Digital |
| 961 | |a paper_00283045_v65_n4_p353_Malaguti |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 74862 | ||