3 papers
cs.DS2026
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…
cs.DS2025
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 algor…
cs.DS2024
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…