Zobrazeno 1 - 10
of 21
pro vyhledávání: '"de Vos, Tijn"'
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, [Thorup, Comb. 2007] used them to obtain his dynamic min-cut algorithm w
Externí odkaz:
http://arxiv.org/abs/2405.09141
Autor:
Dory, Michal, Forster, Sebastian, Kirkpatrick, Yael, Nazari, Yasamin, Williams, Virginia Vassilevska, de Vos, Tijn
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 $2$-approximate APSP in $\tilde O(n^{2.5-r}+n^{\omega(r)})$ time, for any $r\in[0,1]$.
Externí odkaz:
http://arxiv.org/abs/2307.09258
Publikováno v:
EPTCS 390, 2023, pp. 236-252
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 energy game, the vertices of a weighted directed graph belong either to A
Externí odkaz:
http://arxiv.org/abs/2307.08442
Autor:
Forster, Sebatian, de Vos, Tijn
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 how to solve a Laplacian system up to precision $\epsilon$ in $n^{o(1)}\
Externí odkaz:
http://arxiv.org/abs/2304.02315
Autor:
de Vos, Tijn
We consider the CONGEST model on a network with $n$ nodes, $m$ edges, diameter $D$, and integer costs and capacities bounded by $\text{poly} n$. In this paper, we show how to find an exact solution to the minimum cost flow problem in $n^{1/2+o(1)}(\s
Externí odkaz:
http://arxiv.org/abs/2304.01600
We provide new tradeoffs between approximation and running time for the decremental all-pairs shortest paths (APSP) problem. For undirected graphs with $m$ edges and $n$ nodes undergoing edge deletions, we provide four new approximate decremental APS
Externí odkaz:
http://arxiv.org/abs/2211.01152
Autor:
Forster, Sebastian, de Vos, Tijn
In this paper, we bring the main tools of the Laplacian paradigm to the Broadcast Congested Clique. We introduce an algorithm to compute spectral sparsifiers in a polylogarithmic number of rounds, which directly leads to an efficient Laplacian solver
Externí odkaz:
http://arxiv.org/abs/2205.12059
Autor:
van Apeldoorn, Joran, de Vos, Tijn
The Quantum CONGEST model is a variant of the CONGEST model, where messages consist of $O(\log(n))$ qubits. We give a general framework for implementing quantum query algorithms in Quantum CONGEST, using the concept of parallel-queries. We apply our
Externí odkaz:
http://arxiv.org/abs/2202.10969
Autor:
Forster, Sebastian, de Vos, Tijn
A cut sparsifier is a reweighted subgraph that maintains the weights of the cuts of the original graph up to a multiplicative factor of $(1\pm\epsilon)$. This paper considers computing cut sparsifiers of weighted graphs of size $O(n\log (n)/\epsilon^
Externí odkaz:
http://arxiv.org/abs/2112.03120
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 and there are relatively few spanner edges between clusters. In this
Externí odkaz:
http://arxiv.org/abs/2111.08975