A tabu search heuristic for the equitable coloring problem | ||
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario | |
| dc.conicet.organizacion | Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario | |
| dc.conicet.organizacion | Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura | |
| dc.contributor.author | Méndez-díaz, Isabel | |
| dc.contributor.author | Nasini, Graciela Leonor | |
| dc.contributor.author | Severin, Daniel Esteban | |
| dc.date.issued | 2014-03 | |
| dc.description.abstract | The Equitable Coloring Problem is a variant of the Graph Coloring Problem where the sizes of two arbitrary color classes differ in at most one unit. This additional condition, called equity constraints, arises naturally in several applications. Due to the hardness of the problem, current exact algorithms can not solve large-sized instances. Such instances must be addressed only via heuristic methods. In this paper we present a tabu search heuristic for the Equitable Coloring Problem. This algorithm is an adaptation of the dynamic TabuCol version of Galinier and Hao. In order to satisfy equity constraints, new local search criteria are given. Computational experiments are carried out in order to find the best combination of parameters involved in the dynamic tenure of the heuristic. Finally, we show the good performance of our heuristic over known benchmark instances. | es |
| dc.description.fil | Fil: Méndez-díaz, Isabel. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina | |
| dc.description.fil | Fil: Nasini, Graciela Leonor. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; Argentina | |
| dc.description.fil | Fil: Severin, Daniel Esteban. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; Argentina | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Méndez-díaz, Isabel; Nasini, Graciela Leonor; Severin, Daniel Esteban; A tabu search heuristic for the equitable coloring problem; Springer-v D I Verlag Gmbh; Lecture Notes in Computer Science; 8596; 3-2014; 347-358 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0302-9743 | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/29979 | |
| dc.journal.ciudad | Berlín | es |
| dc.journal.pagination | 347-358 | es |
| dc.journal.pais | Alemania | es |
| dc.journal.title | Lecture Notes in Computer Science | es |
| dc.journal.volume | 8596 | es |
| dc.language.iso | eng | es |
| dc.publisher | Springer-v D I Verlag Gmbh | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://link.springer.com/chapter/10.1007%2F978-3-319-09174-7_30 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1007/978-3-319-09174-7_30 | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/2.5/ar/ | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/2.5/ar/ | * |
| dc.subject | Combinatorial Optimization | es |
| dc.subject | Equitable Coloring | es |
| dc.subject | Tabu Search | es |
| dc.subject.classification | Ciencias de la Computación | es |
| dc.subject.classification | Ciencias de la Computación e Información | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | A tabu search heuristic for the equitable coloring problem | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.7d1feb58-6d57-46a6-9d27-dbc98a78533e_A.pdf
- Tamaño:
- 179.32 KB
- Formato:
- Adobe Portable Document Format