Gravitational swarm for graph coloring

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

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

Fecha de defensa: 27 de de juliol de 2012

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

Tipus: Tesi

Teseo: 115421 DIALNET

Resum

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.