Graph col­or­ing in dif­fer­ent amoe­bot mod­els

Abstract: 
The amoebot model is a model of the concept of programmable matter, 
in which tiny processors called amoebots work as distributed actors 
to solve problems in the global model structure. This model, along 
with its necessary limitations, introduces a new perspective on 
well-studied distributed algorithms. 

We mainly focus on the concept of amoebot regions, where the amoebot 
structure is split into many regions of amoebots, and we solve 
problems on these regions. 

We examine the graph coloring problem with regard to different 
configurations of the amoebot model. The graph coloring problem is a 
well-studied graph theory problem in which a graph's vertices are 
colored so that no neighboring vertices share the same color. We aim 
to solve this problem in different configurations of the amoebot 
model and introduce algorithms to color some structures in 
polylogarithmic time and others in linear time. 

We present polylogarithmic probabilistic approaches to 3- or 7-color 
the amoebot structure and, building on that, we present two 
solutions for the 7-coloring of regions of amoebots, to show a 
trade-off between a probabilistic O(r+ log²n) approach and a 
probabilistic O(r log² r + log n) approach. 

In a last step, we reduce the 7-coloring to a 6-coloring in O(r 
log² r + log n) rounds w.h.p.