Tesis doctoral de Israel Carlos Rebollo Ruiz
Abstract:this thesis deals with the development of a swarm intelligence algorithm to solve theclassical problem of graph coloring. The gravitational swarm for graph coloring(gs-gc) algorithm maps the gcp problem into a collection of autonomous agents thatmove in a space following a global gravitational attraction to the color goals andattraction-repulsion local forces corresponding to the graph topology. The thesisprovides formal asymptotic convergence proofs showing that the gs-gc stationarystates correspond to gcp solutions. The thesis provides also extensive empiricalsupport of the gs-gc comparing it with state of the art algorithms.Esta tesis aborda el desarrollo de un algoritmo swarm intelligence para resolver elproblema clásico del coloreado de grafos. El algoritmo gravitational swarm for graphcoloring (gs-gc) mapea el problema gcp en una colección de agentes autónomosque se mueven en un espacio siguiendo una atracción gravitacional global hacia lasmetas de color y unas fuerzas de atracción-repulsión locales que corresponden a latopología del grafo. La tesis ofrece pruebas formales de convergencia asintótica quemuestran que los estados estacionarios del gs-gc corresponden a soluciones de gcp.La tesis ofrece también un amplio soporte empírico al gs-gc comparado conalgoritmos avanzados del estado del arte.
Datos académicos de la tesis doctoral «Gravitational swarm for graph coloring«
- Título de la tesis: Gravitational swarm for graph coloring
- Autor: Israel Carlos Rebollo Ruiz
- Universidad: País vasco/euskal herriko unibertsitatea
- Fecha de lectura de la tesis: 27/07/2012
Dirección y tribunal
- Director de la tesis
- Manuel Graña Romay
- Tribunal
- Presidente del tribunal: Juan Pavon mestras
- Javier De lope asiaín (vocal)
- richard José Duro fernandez (vocal)
- diego Andina de la fuente (vocal)