dc.contributor.author | Orden Martín, David | |
dc.contributor.author | Marsá Maestre, Iván | |
dc.contributor.author | Giménez Guzmán, José Manuel | |
dc.contributor.author | Hoz de la Hoz, Enrique de la | |
dc.date.accessioned | 2016-11-04T09:36:50Z | |
dc.date.issued | 2016-10-17 | |
dc.identifier.bibliographicCitation | Electronic Notes in Discrete Mathematics, 2016, vol. 54, pp. 63-68. | en |
dc.identifier.issn | 1571-0653 | |
dc.identifier.uri | http://hdl.handle.net/10017/26759 | |
dc.description.abstract | We propose two vertex-coloring problems for graphs, endorsing the spectrum of colors with a matrix of interferences between pairs of colors. In the Threshold Spectrum Coloring problem, the number of colors is fixed and the aim is to minimize the maximum interference at a vertex (interference threshold). In the Chromatic Spectrum Coloring problem, a threshold is settled and the aim is to minimize the number of colors (among the available ones) for which respecting that threshold is possible. We prove general upper bounds for the solutions to each problem, valid for any graph and any matrix of interferences. We also show that both problems are NP-hard and perform experimental results, proposing a DSATUR-based heuristic for each problem, in order to study the gap between the theoretical upper bounds and the values obtained. | en |
dc.description.sponsorship | Ministerio de Economía y Competitividad | es_ES |
dc.description.sponsorship | Comunidad de Madrid | es_ES |
dc.format.mimetype | application/pdf | en |
dc.language.iso | eng | en |
dc.rights | Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) | |
dc.rights | Elsevier | |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-sa/4.0/ | |
dc.subject | Graph coloring | en |
dc.subject | Threshold spectrum coloring | en |
dc.subject | Chromatic spectrum coloring | en |
dc.subject | DSATUR | en |
dc.subject | Frequency assignment | en |
dc.subject | WiFi channel assignment | en |
dc.title | Bounds on spectrum graph coloring | en |
dc.type | info:eu-repo/semantics/article | en |
dc.contributor.affiliation | Universidad de Alcalá. Departamento de Automática | es_ES |
dc.contributor.affiliation | Universidad de Alcalá. Departamento de Física y Matemáticas | es_ES |
dc.date.updated | 2016-11-03T12:23:04Z | |
dc.relation.publisherversion | http://dx.doi.org/10.1016/j.endm.2016.09.012 | |
dc.type.version | info:eu-repo/semantics/acceptedVersion | en |
dc.identifier.doi | 10.1016/j.endm.2016.09.012 | |
dc.relation.projectID | info:eu-repo/grantAgreement/MINECO//MTM2014-54207-P/ES/COMBINATORIA Y COMPLEJIDAD DE ESTRUCTURAS GEOMETRICAS DISCRETAS/ | en |
dc.relation.projectID | info:eu-repo/grantAgreement/MINECO//TIN 2014-61627-EXP/ES/DIVIDE AND NOT CONQUER-COMPORTAMIENTOS EMERGENTES EN REDES COMPLEJAS EGOISTAS/ | en |
dc.relation.projectID | info:eu-repo/grantAgreement/CAM//S2013%2FICE-2919/ES/TECNOLOGIAS INTEGRADAS DE GESTION Y OPERACIÓN DE RED 5G/TIGRE5-CM | en |
dc.date.embargoEndDate | 2018-10-17 | |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | en |
dc.identifier.uxxi | AR/0000024885 | |
dc.identifier.publicationtitle | Electronic Notes in Discrete Mathematics | en |
dc.identifier.publicationvolume | 54 | |
dc.identifier.publicationlastpage | 68 | |
dc.identifier.publicationfirstpage | 63 | |