Estudio de limitaciones teóricas y aproximaciones computacionales al problema del coloreado espectral de grafos
Autores
Álvarez Suárez, AnaFecha de publicación
2016Palabras clave
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
Tipo de documento
info:eu-repo/semantics/bachelorThesis
Versión
info:eu-repo/semantics/acceptedVersion
Derechos
Atribución-NoComercial-SinDerivadas 3.0 España
Derechos de acceso
info:eu-repo/semantics/openAccess
Resumen
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.
Ficheros en el ítem
Ficheros | Tamaño | Formato |
|
---|---|---|---|
TFG-Alvarez-Suarez-2016.pdf | 4.082Mb |
|
Ficheros | Tamaño | Formato |
|
---|---|---|---|
TFG-Alvarez-Suarez-2016.pdf | 4.082Mb |
|