Bounds on spectrum graph coloring
Autores
Orden Martín, David; Marsá Maestre, Iván; Giménez Guzmán, José Manuel; Hoz de la Hoz, Enrique de laIdentificadores
Enlace permanente (URI): http://hdl.handle.net/10017/26759DOI: 10.1016/j.endm.2016.09.012
ISSN: 1571-0653
Fecha de publicación
2016-10-17Fecha fin de embargo
2018-10-17Filiación
Universidad de Alcalá. Departamento de Automática; Universidad de Alcalá. Departamento de Física y MatemáticasPatrocinadores
Ministerio de Economía y Competitividad
Comunidad de Madrid
Cita bibliográfica
Electronic Notes in Discrete Mathematics, 2016, vol. 54, pp. 63-68.
Palabras clave
Graph coloring
Threshold spectrum coloring
Chromatic spectrum coloring
DSATUR
Frequency assignment
WiFi channel assignment
Proyectos
info:eu-repo/grantAgreement/MINECO//MTM2014-54207-P/ES/COMBINATORIA Y COMPLEJIDAD DE ESTRUCTURAS GEOMETRICAS DISCRETAS/
info:eu-repo/grantAgreement/MINECO//TIN 2014-61627-EXP/ES/DIVIDE AND NOT CONQUER-COMPORTAMIENTOS EMERGENTES EN REDES COMPLEJAS EGOISTAS/
info:eu-repo/grantAgreement/CAM//S2013%2FICE-2919/ES/TECNOLOGIAS INTEGRADAS DE GESTION Y OPERACIÓN DE RED 5G/TIGRE5-CM
Tipo de documento
info:eu-repo/semantics/article
Versión
info:eu-repo/semantics/acceptedVersion
Versión del editor
http://dx.doi.org/10.1016/j.endm.2016.09.012Derechos
Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)
Elsevier
Derechos de acceso
info:eu-repo/semantics/openAccess
Resumen
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.
Ficheros en el ítem
Ficheros | Tamaño | Formato |
|
---|---|---|---|
Bounds_on_spectrum__JMDA__2016.pdf | 1.062Mb |
|
Ficheros | Tamaño | Formato |
|
---|---|---|---|
Bounds_on_spectrum__JMDA__2016.pdf | 1.062Mb |
|
Colecciones
- AUTOMATIC - Artículos [144]