The thesis aims to solve graph-coloring problems within different variations of the amoebot model, an abstraction of programmable matter, where a each vertex is a assigned a color matching no neighboring color. Understanding efficient coloring using the underlying structure and restrictions of the amoebot model and comparison with other distributed algorithms is essential for developing higher level algorithms. The central question of the paper is how can we efficiently color the graph induced by regions of amoebots, where many neighboring amoebots build a region and a structure of many of these regions have to be colored and what is the least amount of colors we can use, while not increasing the runtime too much.
Wednesday, 11.02.2026
| 14.00 to 14.30 h
Graph coloring in different amoebot models
Location: F2.419
Organizer: Nils Pape, Bachelorantrittsvortrag
Organizer: Nils Pape, Bachelorantrittsvortrag