Estudio de limitaciones teóricas y aproximaciones computacionales al problema del coloreado espectral de grafos
Authors
Álvarez Suárez, AnaDate
2016Keywords
Coloración de grafos
Interferencias electromagnéticas
Threshold spectrum coloring
Chromatic spectrum coloring
Radio frecuencia
Redes locales inalámbricas
Triangulación
DSATUR
ALHSO
ALPSO
NetworkX
Document type
info:eu-repo/semantics/bachelorThesis
Version
info:eu-repo/semantics/acceptedVersion
Rights
Atribución-NoComercial-SinDerivadas 3.0 España
Access rights
info:eu-repo/semantics/openAccess
Abstract
Dentro de los problemas de coloración de grafos, muchos existen en respuesta a una situación práctica. Para el caso de la asignación de canales en IEEE 802.11,
se añade al planteamiento una matriz de distancias o "interferencias" entre los
colores, lo cual da lugar al problema del espectro de umbrales, que fija el número de colores disponible y minimiza la máxima interferencia en un vértice, y a su
complementario, el problema del coloreado espectral.
De ambos se conocen cotas superiores generales pero amplias. En este trabajo, se han mejorado dichas cotas para algunos tipos de grafos, utilizando herramientas teóricas y computacionales para su comprobación. In the field of graph coloring, most problems arise in response to a practical
situation. For the frequency assignment problem in IEEE 802.11 (WiFi), a distance or "interference" matrix is added, which leads to the Threshold Spectrum
Coloring Problem (TSC), given a fixed number of available colors, minimizes
maximum interference in a vertex, and its complementary, the Chromatic Spectrum Coloring problem (CSC).
General upper bounds are known for both of them. In this paper, these
bounds are improved for diferent types of graphs, using theoretical and computational tools to prove them.
Files in this item
Files | Size | Format |
|
---|---|---|---|
TFG-Alvarez-Suarez-2016.pdf | 4.082Mb |
|
Files | Size | Format |
|
---|---|---|---|
TFG-Alvarez-Suarez-2016.pdf | 4.082Mb |
|