Tesis doctoral de Francisco Javier Ozón Górriz
En la presente tesis se analiza el problema del coloreado de grafos tanto desde le punto de vista teórico como en relación a la resolución del problema mediante técnicas algorítmicas, algunas de las cuales se describen por vez primera. Se estudian asimismo distintas variaciones del problema simple del coloreado incluyendo el coloreado de vértices etiquetados, en que se asigna un número variable de colores a cada vértice,y el coloreado con aristas etiquetadas, en el que los clolores asignados a vértices adayacentes deben guardar una distancia mayor o igual a la etiqueta de la arista que los une, así como combinaciones de ambos. las técnicas descritas para el coloreado de grafos han sido posteriormente adaptadas a un problema de asignación de frecuencias en telefónia móvil habiéndose aplicado los algortimos sobre distintos tipos de redes celulares. las distintas redes analizadas pueden incorporar o no conmutación en frecuencia, variando la naturaleza del problema en cada caso. Para el caso de coloreado múltiple asociado al problema de asignación de frecuencias se ha descrito un conjunto de matrices asociadas a un grafo g(v,e) y un coloreado simple c que permiten reasignar colores a distintos vértices de g(v,e) aprovechando colores de c. Este reciclaje, en combinación con los métodos algorítmicos aplicados en coloreados simples, ha permitido resolver con eficiencia el problema del multicoloreado de grafos y en consecuencia el problema de asignación de frecuencias en redes celulares. en la segunda parte de la tesis se estudian las redes pequeño-mundo y se describen pautas deterministas para su obtención. De este modo se describe en primer luagr el modelo probabilista definido por watts y strogatz y se analiza la aparición de autoorganización crítica en las redes pequño-mundo (caracterizadas por una piñamiento elevado y un diámetro o distancia máxima entre vértices reducido) para a continuación ampliar el co
Datos académicos de la tesis doctoral «Contribución al coloreado de grafos y las redes pequeño-mundo«
- Título de la tesis: Contribución al coloreado de grafos y las redes pequeño-mundo
- Autor: Francisco Javier Ozón Górriz
- Universidad: Politécnica de catalunya
- Fecha de lectura de la tesis: 23/07/2001
Dirección y tribunal
- Director de la tesis
- Francesc Comellas Padró
- Tribunal
- Presidente del tribunal: josep Fí brega canudas
- michael Sampels (vocal)
- josep-maria Basart muñoz (vocal)
- joan Gimbert quintilla (vocal)