21 citations · 28 across the 6 of their papers we have counts for
7 papers
Beeping a Maximal Independent Set Fast
Stephan Holzer, Nancy Lynch
We adapt a recent algorithm by Ghaffari [SODA'16] for computing a Maximal Independent Set in the LOCAL model, so that it works in the significantly weaker BEEP model. For networks…
Distributed Local Multi-Aggregation and Centrality Approximation
Benjamin Dissler, Stephan Holzer, Roger Wattenhofer
We study local aggregation and graph analysis in distributed environments using the message passing model. We provide a flexible framework, where each of the nodes in a set --wh…
A Local Broadcast Layer for the SINR Network Model
Magnus M. Halldorsson, Stephan Holzer, Nancy Lynch
We present the first algorithm that implements an abstract MAC (absMAC) layer in the Signal-to-Interference-plus-Noise-Ratio (SINR) wireless network model. We first prove that effi…
Approximation of Distances and Shortest Paths in the Broadcast Congest Clique
Stephan Holzer, Nathan Pinsker
We study the broadcast version of the CONGEST CLIQUE model of distributed computing. In this model, in each round, any node in a network of size can send the same message (i.e.…
Distributed Approximation of Minimum Routing Cost Trees
Alexandra Hochuli, Stephan Holzer, Roger Wattenhofer
We study the NP-hard problem of approximating a Minimum Routing Cost Spanning Tree in the message passing model with limited bandwidth (CONGEST model). In this problem one tries to…
The Power of Non-Uniform Wireless Power
Magnus M. Halldorsson, Stephan Holzer, Pradipta Mitra +1
We study a fundamental measure for wireless interference in the SINR model known as (weighted) inductive independence. This measure characterizes the effectiveness of using oblivio…
Distributed Verification and Hardness of Distributed Approximation
Atish Das Sarma, Stephan Holzer, Liah Kor +5
We study the {\em verification} problem in distributed networks, stated as follows. Let be a subgraph of a network where each vertex of knows which edges incident on it…