A DSATUR-based algorithm for the Equitable Coloring Problem | ||
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación | |
| 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 | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| 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 | 2015-02 | |
| dc.description.abstract | This paper describes a new exact algorithm for the Equitable Coloring Problem, a coloring problem where the sizes of two arbitrary color classes differ in at most one unit. Based on the well known DSatur algorithm for the classic Coloring Problem, a pruning criterion arising from equity constraints is proposed and analyzed. The good performance of the algorithm is shown through computational experiments over random and benchmark instances. | es |
| dc.description.fil | Fil: Méndez-Díaz, Isabel. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina | |
| dc.description.fil | Fil: Nasini, Graciela Leonor. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina | |
| dc.description.fil | Fil: Severin, Daniel Esteban. Consejo Nacional de Investigaciones Científicas y Técnicas; 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 DSATUR-based algorithm for the Equitable Coloring Problem; Pergamon-Elsevier Science Ltd; Computers & Operations Research; 57; 2-2015; 41-50 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0305-0548 | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/38356 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.pagination | 41-50 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Computers & Operations Research | es |
| dc.journal.volume | 57 | es |
| dc.language.iso | eng | es |
| dc.publisher | Pergamon-Elsevier Science Ltd | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/http://www.sciencedirect.com/science/article/pii/S0305054814003189 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.cor.2014.11.014 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://arxiv.org/abs/1306.1758 | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/2.5/ar/ | * |
| dc.subject | Dsatur | es |
| dc.subject | Equitable Coloring | es |
| dc.subject | Exact Algorithm | 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 DSATUR-based algorithm 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.20b4fa34-399d-43e9-9366-6ba511fc701d_A.pdf
- Tamaño:
- 322.12 KB
- Formato:
- Adobe Portable Document Format