Gravitational swarm for graph coloring

  1. REBOLLO RUIZ, ISRAEL CARLOS
Dirigida por:
  1. Manuel Graña Romay Director

Universidad de defensa: Universidad del País Vasco - Euskal Herriko Unibertsitatea

Fecha de defensa: 27 de julio de 2012

Tribunal:
  1. Juan Luis Pavón Mestras Presidente/a
  2. Ana Isabel González Acuña Secretaria
  3. Javier de Lope Asiaín Vocal
  4. Richard J. Duro Fernández Vocal
  5. Diego Andina de la Fuente Vocal

Tipo: Tesis

Teseo: 115421 DIALNET

Resumen

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.