5 citations · 7 across the 18 of their papers we have counts for
28 papers · 1 filter
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…
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…
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 pa…
Distributed Santa Claus via Global Rounding
Tijn de Vos, Leo Wennmann, Malte Baumecker +2
In this paper, we initiate the study of a new class of problems in the CONGEST model: Mixed packing and covering linear programs (LP). Previously, the design of optimization algori…
Fast Deterministic Distributed Degree Splitting
Yannic Maus, Alexandre Nolin, Florian Schager
We obtain better algorithms for computing more balanced orientations and degree splits in LOCAL. Important to our result is a connection to the hypergraph sinkless orientation prob…
Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors
Maxime Flin, Magnús M. Halldórsson, Manuel Jakob +1
For any , let be the maximum integer such that . We give a distributed \LOCAL algorithm that, given an integer , computes a valid -color…