15 papers
Distributed Symmetry Breaking on Hyperbolic Random Graphs
Yannic Maus, Janosch Ruff, Sonia Simons +1
Real-world networks like the internet share patterns like a power law degree distribution and a high clustering coefficient. Many of these properties are captured by the generative…
Robust Shattering Arguments
Mohsen Ghaffari, Magnús M. Halldórsson, Yannic Maus +1
Graph shattering is a central technique underlying sublogarithmic-time distributed algorithms in the LOCAL model. Its analysis typically relies on bounding the probability that lar…
Distributed Sparsest Cut via Eigenvalue Estimation
Yannic Maus, Tijn de Vos
We give new, improved bounds for approximating the sparsest cut value or in other words the conductance of a graph in the CONGEST model. As our main result, we present an algo…
Near-Optimal Distributed 2-Ruling Sets on Graphs with Low Arboricity
Malte Baumecker, Rustam Latypov, Yannic Maus +1
Given a graph , a -ruling set is a subset of nodes that is independent, and each node in is at distance at most from some node in . In this…
Deterministic Distance Approximation in MPC via Improved Hitting Sets
Kyungjin Cho, Michal Dory, Yannic Maus +1
In this paper, we provide the first deterministic algorithms with sublogarithmic round complexity for spanners and approximate shortest paths in various MPC models. Moreover, we si…
Distributed Santa Claus via Global Rounding
Tijn de Vos, Leo Wennmann, Malte Baumecker +2
In this paper, we consider the Santa Claus problem in the CONGEST model. This NP-hard problem can be modeled as a bipartite graph of children and gifts where an edge indicates that…