Gravitational swarm for graph coloring

Supervised by:
  1. Manuel Graña Romay Director

Defence university: Universidad del País Vasco - Euskal Herriko Unibertsitatea

Fecha de defensa: 27 July 2012

  1. Juan Luis Pavón Mestras Chair
  2. Ana Isabel González Acuña Secretary
  3. Javier de Lope Asiaín Committee member
  4. Richard J. Duro Fernández Committee member
  5. Diego Andina de la Fuente Committee member
  1. Ciencia de la Computación e Inteligencia Artificial

Type: Thesis

Teseo: 115421 DIALNET


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.