14 citations · 15 across the 8 of their papers we have counts for
11 papers
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…
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…
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…
Fast 2-Approximate All-Pairs Shortest Paths
Michal Dory, Sebastian Forster, Yael Kirkpatrick +3
In this paper, we revisit the classic approximate All-Pairs Shortest Paths (APSP) problem in undirected graphs. For unweighted graphs, we provide an algorithm for -approximate A…
Fast Algorithms for Energy Games in Special Cases
Sebastian Forster, Antonis Skarlatos, Tijn de Vos
In this paper, we study algorithms for special cases of energy games, a class of turn-based games on graphs that show up in the quantitative analysis of reactive systems. In an ene…
The Laplacian Paradigm in Deterministic Congested Clique
Sebatian Forster, Tijn de Vos
In this paper, we bring the techniques of the Laplacian paradigm to the congested clique, while further restricting ourselves to deterministic algorithms. In particular, we show ho…
Minimum Cost Flow in the CONGEST Model
Tijn de Vos
We consider the CONGEST model on a network with nodes, edges, diameter , and integer costs and capacities bounded by . In this paper, we show how to find…
New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
Michal Dory, Sebastian Forster, Yasamin Nazari +1
We provide new tradeoffs between approximation and running time for the decremental all-pairs shortest paths (APSP) problem. For undirected graphs with edges and nodes unde…
A Framework for Distributed Quantum Queries in the CONGEST Model
Joran van Apeldoorn, Tijn de Vos
The Quantum CONGEST model is a variant of the CONGEST model, where messages consist of qubits. We give a general framework for implementing quantum query algorithms in…
Faster Cut Sparsification of Weighted Graphs
Sebastian Forster, Tijn de Vos
A cut sparsifier is a reweighted subgraph that maintains the weights of the cuts of the original graph up to a multiplicative factor of . This paper considers computing cu…
An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions
Sebastian Forster, Martin Grösbacher, Tijn de Vos
Spanners have been shown to be a powerful tool in graph algorithms. Many spanner constructions use a certain type of clustering at their core, where each cluster has small diameter…