Patterns from nature: Distributed greedy colouring with simple messages and minimal graph knowledge
Patterns from nature: Distributed greedy colouring with simple messages and minimal graph knowledge
复制标题
来自自然的模式：具有简单消息和最少图形知识的分布式贪婪着色
DOI：
10.1016/j.ins.2014.06.035
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
P. Jeavons
中科院分区：
文献类型：
--
作者：
Lei Xu;P. Jeavons
全局优化中的一个公认的问题是使用最少数量的颜色对任意图的顶点进行着色的问题，使得相邻的顶点被分配不同的颜色。一种限制使用颜色数量的方法是只允许贪婪着色。贪婪着色是一种将颜色分配给图的顶点的算法，该算法依次考虑每个顶点并将尚未分配给某个邻居的第一种颜色分配给该顶点。最佳的着色总是可以通过这种方式获得，通过选择一个适当的顺序上的vertex.Recently，一个新的生物启发的方法，分布式模式的形成已被提出，基于模拟的神经发育的果蝇。基于这种方法，我们提出了一个新的简单的随机算法，分布式贪婪着色只使用本地处理的顶点和消息沿着的边缘。在我们的方法中，处理器只交换代表潜在颜色值的简单消息，并且每个处理器具有最少的图形知识。我们讨论了该算法的两种变体，并从理论和实验上研究了它们的时间复杂度和消息复杂度，此外，我们还通过实验证明了所使用的颜色数对于许多标准图着色基准来说是最优或接近最优的。因此，对于分布式网络，我们的算法作为一个有效的启发式方法来计算着色与少量的颜色。
A well-established problem in global optimization is the problem of colouring the vertices of an arbitrary graph using the minimal number of colours, such that adjacent vertices are assigned different colours. One way to restrict the number of colours used is to allow only greedy colourings. A greedy colouring is an assignment of colours to the vertices of a graph that can be obtained by an algorithm that considers each vertex in turn and assigns the first colour that is not already assigned to some neighbour. An optimal colouring can always be obtained in this way, by choosing an appropriate order on the vertices.Recently, a new bio-inspired approach to distributed pattern formation has been proposed, based on modelling the neurological development of the fruit fly. Building on that approach, we propose a new simple randomised algorithm for distributed greedy colouring using only local processing at the vertices and messages along the edges. In our approach the processors exchange only simple messages representing potential colour values and each processor has minimal graph knowledge. We discuss two variations of this algorithm, and investigate their time complexity and message complexity both theoretically and experimentally.In addition, we show experimentally that the number of colours used turns out to be optimal or near-optimal for many standard graph colouring benchmarks. Thus, for distributed networks, our algorithm serves as an effective heuristic approach to computing a colouring with a small number of colours.