Gravitational swarm for graph coloring

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

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

Fecha de defensa: 27 de xullo 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 Vogal
  4. Richard J. Duro Fernández Vogal
  5. Diego Andina de la Fuente Vogal

Tipo: Tese

Teseo: 115421 DIALNET

Resumo

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.