Gravitational swarm for graph coloring

  1. REBOLLO RUIZ, ISRAEL CARLOS
Dirigée par:
  1. Manuel Graña Romay Directeur

Université de défendre: Universidad del País Vasco - Euskal Herriko Unibertsitatea

Fecha de defensa: 27 juillet 2012

Jury:
  1. Juan Luis Pavón Mestras President
  2. Ana Isabel González Acuña Secrétaire
  3. Javier de Lope Asiaín Rapporteur
  4. Richard J. Duro Fernández Rapporteur
  5. Diego Andina de la Fuente Rapporteur

Type: Thèses

Teseo: 115421 DIALNET

Résumé

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.