摘要翻译：
图着色，也称为顶点着色，考虑给图的结点分配颜色的问题，使得相邻结点不共享相同的颜色。该问题的优化版本涉及到使用的颜色数量的最小化。本文用一种只利用局部信息来确定结点颜色的算法，以分布式的方式解决了图的有效着色问题。这样的算法来自任何中央控制。由于许多实际应用需要以分布式的方式来寻找图的着色，因此在过去的十年里，人们对图着色的分布式算法越来越感兴趣。以无线ad-hoc和传感器网络为例，在这些网络中，频率分配或TDMA时隙分配等任务都与图着色密切相关。本文提出的算法受到了日本树蛙叫唤行为的启发。雄性青蛙用它们的叫声来吸引雌性。有趣的是，位于彼此附近的雄性群体会使它们的叫声不同步。这是因为雌性青蛙只有在它们的叫声不是太近的时候才能正确地定位雄性青蛙。我们的实验表明，我们的算法是非常有竞争力的当前的技术，使用不同的问题实例集，并与文献中最有竞争力的算法之一进行比较。
---
英文标题：
《Distributed Graph Coloring: An Approach Based on the Calling Behavior of
  Japanese Tree Frogs》
---
作者：
Hugo Hern\'andez and Christian Blum
---
最新提交年份：
2010
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--

---
英文摘要：
  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 used colors. In this paper we deal with the problem of finding valid colorings of graphs in a distributed way, that is, by means of an algorithm that only uses local information for deciding the color of the nodes. Such algorithms prescind from any central control. Due to the fact that quite a few practical applications require to find colorings in a distributed way, the interest in distributed algorithms for graph coloring has been growing during the last decade. As an example consider wireless ad-hoc and sensor networks, where tasks such as the assignment of frequencies or the assignment of TDMA slots are strongly related to graph coloring.   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 nearby each other desynchronize their calls. This is because female frogs are only able to correctly localize the male frogs when their calls are not too close in time. 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.
---
PDF链接：
https://arxiv.org/pdf/1011.5349