5 papers · 1 filter
Distributed And Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs
Jinfeng Dou, Thorsten Götte, Henning Hillebrandt +2
We consider the distributed and parallel construction of low-diameter decompositions with strong diameter for (weighted) graphs and (weighted) graphs that can be separated through…
The Max-Line-Formation Problem
Jannik Castenow, Thorsten Götte, Till Knollmann +1
We consider n robots with limited visibility: each robot can observe other robots only up to a constant distance denoted as the viewing range. The robots operate in discrete rounds…
Beep-And-Sleep: Message and Energy Efficient Set Cover
Thorsten Götte, Christina Kolb, Christian Scheideler +1
We observe message-efficient distributed algorithms for the Set Cover problem. Given a ground set of elements and subsets of , we aim to find the minimal number of t…
Always be Two Steps Ahead of Your Enemy
Thorsten Götte, Vipin Ravindran Vijayalakshmi, Christian Scheideler
We investigate the maintenance of overlay networks under massive churn, i.e. nodes joining and leaving the network. We assume an adversary that may churn a constant fraction o…
On Underlay-Aware Self-Stabilizing Overlay Networks
Thorsten Götte, Christian Scheideler, Alexander Setzer
We present a self-stabilizing protocol for an overlay network that constructs the Minimum Spanning Tree (MST) for an underlay that is modeled by a weighted tree. The weight of an o…