38 citations · 178 across the 46 of their papers we have counts for
28 papers · 1 filter
On the Node-Averaged Complexity of Locally Checkable Problems on Trees
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +2
Over the past decade, a long line of research has investigated the distributed complexity landscape of locally checkable labeling (LCL) problems on bounded-degree graphs, culminati…
Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem
Mélanie Cambus, Fabian Kuhn, Shreyas Pai +1
In this work, we present a constant-round algorithm for the -ruling set problem in the Congested Clique model. As a direct consequence, we obtain a constant round algorithm in t…
Distributed Maximal Matching and Maximal Independent Set on Hypergraphs
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +1
We investigate the distributed complexity of maximal matching and maximal independent set (MIS) in hypergraphs in the LOCAL model. A maximal matching of a hypergraph …
Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond
Salwa Faour, Mohsen Ghaffari, Christoph Grunau +2
We develop a general deterministic distributed method for locally rounding fractional solutions of graph problems for which the analysis can be broken down into analyzing pairs of…
Contention Resolution for Coded Radio Networks
Michael A. Bender, Seth Gilbert, Fabian Kuhn +2
Randomized backoff protocols, such as exponential backoff, are a powerful tool for managing access to a shared resource, often a wireless communication channel (e.g., [1]). For a w…
Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings
Salwa Faour, Marc Fuchs, Fabian Kuhn
We provide CONGEST model algorithms for approximating minimum weighted vertex cover and the maximum weighted matching. For bipartite graphs, we show that a -approx…