1 citations · 1 across the 4 of their papers we have counts for
15 papers
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 …
Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +1
Recently, Balliu, Brandt, and Olivetti [FOCS '20] showed the first lower bound for the maximal independent set (MIS) problem in trees. In this work we prove lower bou…
Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma
Sebastian Brandt, Christoph Grunau, Václav Rozhoň
Recently, Brandt, Maus and Uitto [PODC'19] showed that, in a restricted setting, the dependency of the complexity of the distributed Lovász Local Lemma (LLL) on the chosen LLL crit…
Tight Bounds for Deterministic High-Dimensional Grid Exploration
Sebastian Brandt, Julian Portmann, Jara Uitto
We study the problem of exploring an oriented grid with autonomous agents governed by finite automata. In the case of a 2-dimensional grid, the question how many agents are require…
Efficient Load-Balancing through Distributed Token Dropping
Sebastian Brandt, Barbara Keller, Joel Rybicki +2
We introduce a new graph problem, the token dropping game, and we show how to solve it efficiently in a distributed setting. We use the token dropping game as a tool to design an e…
Truly Tight-in- Bounds for Bipartite Maximal Matching and Variants
Sebastian Brandt, Dennis Olivetti
In a recent breakthrough result, Balliu et al. [FOCS'19] proved a deterministic -round and a randomized -ro…