Zobrazeno 1 - 10
of 286
pro vyhledávání: '"HAEUPLER, BERNHARD"'
We give the first parallel algorithm with optimal $\tilde{O}(m)$ work for the classical problem of computing Single-Source Shortest Paths in general graphs with negative-weight edges. In graphs without negative edges, Dijkstra's algorithm solves the
Externí odkaz:
http://arxiv.org/abs/2410.20959
While Dijkstra's algorithm has near-optimal time complexity for the problem of finding the shortest $st$-path, in practice, other algorithms are often superior on huge graphs. A prominent such example is the bidirectional search, which executes Dijks
Externí odkaz:
http://arxiv.org/abs/2410.14638
In this work, we study two-party interactive coding for adversarial noise, when both parties have limited memory. We show how to convert any adaptive protocol $\Pi$ into a protocol $\Pi'$ that is robust to an $\epsilon$-fraction of adversarial corrup
Externí odkaz:
http://arxiv.org/abs/2408.06541
We introduce the concept of low-step multi-commodity flow emulators for any undirected, capacitated graph. At a high level, these emulators contain approximate multi-commodity flows whose paths contain a small number of edges, shattering the infamous
Externí odkaz:
http://arxiv.org/abs/2406.14384
Expander decompositions form the basis of one of the most flexible paradigms for close-to-linear-time graph algorithms. Length-constrained expander decompositions generalize this paradigm to better work for problems with lengths, distances and costs.
Externí odkaz:
http://arxiv.org/abs/2404.13446
Autor:
Haeupler, Bernhard, Hladík, Richard, Iacono, John, Rozhon, Vaclav, Tarjan, Robert, Tětek, Jakub
We consider the problem of sorting $n$ items, given the outcomes of $m$ pre-existing comparisons. We present a simple and natural deterministic algorithm that runs in $O(m+\log T)$ time and does $O(\log T)$ comparisons, where $T$ is the number of tot
Externí odkaz:
http://arxiv.org/abs/2404.04552
This paper addresses point-to-point packet routing in undirected networks, which is the most important communication primitive in most networks. The main result proves the existence of routing tables that guarantee a polylog-competitive completion-ti
Externí odkaz:
http://arxiv.org/abs/2403.07410
We present a new distance oracle in the fully dynamic setting: given a weighted undirected graph $G=(V,E)$ with $n$ vertices undergoing both edge insertions and deletions, and an arbitrary parameter $\epsilon$ where $\epsilon\in[1/\log^{c} n,1]$ and
Externí odkaz:
http://arxiv.org/abs/2402.18541
This paper proves that Dijkstra's shortest-path algorithm is universally optimal in both its running time and number of comparisons when combined with a sufficiently efficient heap data structure. Universal optimality is a powerful beyond-worst-case
Externí odkaz:
http://arxiv.org/abs/2311.11793
We study a new and stronger notion of fault-tolerant graph structures whose size bounds depend on the degree of the failing edge set, rather than the total number of faults. For a subset of faulty edges $F \subseteq G$, the faulty-degree $\deg(F)$ is
Externí odkaz:
http://arxiv.org/abs/2309.06696