Carregant...
Carregant...

Vés al contingut (premeu Retorn)

FrogCOL and FrogMIS: new decentralized algorithms for finding large independent sets in graphs

Autor
Blum, C.; Calvo, B.; Blesa, M.
Tipus d'activitat
Article en revista
Revista
Swarm intelligence
Data de publicació
2015-09-01
Volum
9
Número
2-3
Pàgina inicial
205
Pàgina final
227
DOI
https://doi.org/10.1007/s11721-015-0110-1 Obrir en finestra nova
Projecte finançador
Métodos formales y algoritmos para el diseño de sistemas
Repositori
http://hdl.handle.net/2117/77894 Obrir en finestra nova
URL
http://link.springer.com/article/10.1007/s11721-015-0110-1 Obrir en finestra nova
Resum
Finding large (and generally maximal) independent sets of vertices in a given graph is a fundamental problem in distributed computing. Applications include, for example, facility location and backbone formation in wireless ad hoc networks. In this paper, we study a decentralized (or distributed) algorithm inspired by the calling behavior of male Japanese tree frogs, originally introduced for the graph-coloring problem, for its potential usefulness in the context of finding large independent sets...
Citació
Blum, C., Calvo, B., Blesa, M. FrogCOL and FrogMIS: new decentralized algorithms for finding large independent sets in graphs. "Swarm intelligence", 01 Setembre 2015, vol. 9, núm. 2-3, p. 205-227.
Paraules clau
Swarm Intelligence, Self-desynchronization, Maximal Independent Set, Decentralized Algorithms
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants

Arxius