RT info:eu-repo/semantics/article
T1 Bounds on spectrum graph coloring
A1 Orden Martín, David
A1 Marsá Maestre, Iván
A1 Giménez Guzmán, José Manuel
A1 Hoz de la Hoz, Enrique de la
K1 Graph coloring
K1 Threshold spectrum coloring
K1 Chromatic spectrum coloring
K1 DSATUR
K1 Frequency assignment
K1 WiFi channel assignment
AB 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.
SN 1571-0653
YR 2016
FD 2016-10-17
LK http://hdl.handle.net/10017/26759
UL http://hdl.handle.net/10017/26759
LA eng
NO Ministerio de Economía y Competitividad
DS MINDS@UW
RD 23-abr-2024