6 papers
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…
Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity
Tijn de Vos, Aleksander B. G. Christiansen
A tree-packing is a collection of spanning trees of a graph. It has been a useful tool for computing the minimum cut in static, dynamic, and distributed settings. In particular, [T…
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…
Deterministic Edge Coloring with few Colors in CONGEST
Joakim Blikstad, Yannic Maus, Tijn de Vos
As the main contribution of this work we present deterministic edge coloring algorithms in the CONGEST model. In particular, we present an algorithm that edge colors any -node g…
Dynamic Matroids: Base Packing and Covering
Tijn de Vos, Mara Grilnberger
In this paper, we consider dynamic matroids, where elements can be inserted to or deleted from the ground set over time. The independent sets change to reflect the current ground s…
Towards Constant Time Multi-Call Rumor Spreading on Small-Set Expanders
Emilio Cruciani, Sebastian Forster, Tijn de Vos
We study a multi-call variant of the classic PUSH&PULL rumor spreading process where nodes can contact of their neighbors instead of a single one during both PUSH and PULL oper…