期刊
SWARM INTELLIGENCE
卷 6, 期 2, 页码 117-150出版社
SPRINGER
DOI: 10.1007/s11721-012-0067-2
关键词
Distributed graph coloring; Calling behavior of Japanese tree frogs
资金
- Spanish government [TIN2007-66523]
- EU [FP7-ICT-2007-1]
- Comissionat per a Universitats i Recerca del Departament d'Innovacio, Universitats i Empresa de la Generalitat de Catalunya
- European Social Fund
Graph coloring-also known as vertex coloring-considers the problem of assigning colors to the nodes of a graph such that adjacent nodes do not share the same color. The optimization version of the problem concerns the minimization of the number of colors used. In this paper we deal with the problem of finding valid graphs colorings in a distributed way, that is, by means of an algorithm that only uses local information for deciding the color of the nodes. The algorithm proposed in this paper is inspired by the calling behavior of Japanese tree frogs. Male frogs use their calls to attract females. Interestingly, groups of males that are located near each other desynchronize their calls. This is because female frogs are only able to correctly localize male frogs when their calls are not too close in time. The proposed algorithm makes use of this desynchronization behavior for the assignment of different colors to neighboring nodes. We experimentally show that our algorithm is very competitive with the current state of the art, using different sets of problem instances and comparing to one of the most competitive algorithms from the literature.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据