|
Título:
|
Can frogs find large independent sets in a decentralized way? Yes they can!
|
|
Autor/a:
|
Blum, Christian; Blesa Aguilera, Maria Josep; Calvo, Borja
|
|
Otros autores:
|
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació; Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals |
|
Abstract:
|
The problem of identifying a maximal independent (node) set in a given graph is a fundamental problem in distributed computing. It has numerous applications, for example, in wireless networks in the context of facility location and backbone formation. In this paper we study the ability of a bio-inspired, distributed algorithm, initially proposed for graph coloring, to generate large independent sets. The inspiration of the considered algorithm stems from the self-synchronization capability of Japanese tree frogs. The experimental results confirm, indeed, that the algorithm has a strong tendency towards the generation of colorings in which the set of nodes assigned to the most-used color is rather large. Experimental results are compared to the ones of recent algorithms from the literature. Concerning solution quality, the results show that the frog-inspired algorithm has advantages especially for the application to rather sparse graphs. Concerning the computation round count, the algorithm has the advantage of converging within a reasonable number of iterations, regardless of the size and density of the considered graph. |
|
Abstract:
|
Peer Reviewed |
|
Materia(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
-Graph theory
-Distributed algorithms
-Grafs, Teoria de
-Algorismes distribuïts |
|
Derechos:
|
|
|
Tipo de documento:
|
Artículo - Versión presentada
Objeto de conferencia |
|
Editor:
|
Springer
|
|
Compartir:
|
|
