Recent advances in fully dynamic graph algorithms–a quick reference guide
In recent years, significant advances have been made in the design and analysis of fully
dynamic algorithms. However, these theoretical results have received very little attention …
dynamic algorithms. However, these theoretical results have received very little attention …
Recent advances in fully dynamic graph algorithms
In recent years, significant advances have been made in the design and analysis of fully
dynamic algorithms. However, these theoretical results have received very little attention …
dynamic algorithms. However, these theoretical results have received very little attention …
Dynamic approximate shortest paths and beyond: Subquadratic and worst-case update time
J van den Brand, D Nanongkai - 2019 IEEE 60th Annual …, 2019 - ieeexplore.ieee.org
Consider the following distance query for an n-node graph G undergoing edge insertions
and deletions: given two sets of nodes I and J, return the distances between every pair of …
and deletions: given two sets of nodes I and J, return the distances between every pair of …
Deterministic algorithms for decremental approximate shortest paths: Faster and simpler
MP Gutenberg, C Wulff-Nilsen - Proceedings of the Fourteenth Annual ACM …, 2020 - SIAM
In the decremental (1+ ϵ)-approximate Single-Source Shortest Path (SSSP) problem, we
are given a graph G=(V, E) with n=| V|, m=| E|, undergoing edge deletions, and a …
are given a graph G=(V, E) with n=| V|, m=| E|, undergoing edge deletions, and a …
New algorithms and hardness for incremental single-source shortest paths in directed graphs
M Probst Gutenberg, V Vassilevska Williams… - Proceedings of the 52nd …, 2020 - dl.acm.org
In the dynamic Single-Source Shortest Paths (SSSP) problem, we are given a graph G=(V,
E) subject to edge insertions and deletions and a source vertex s∈ V, and the goal is to …
E) subject to edge insertions and deletions and a source vertex s∈ V, and the goal is to …
Tight dynamic problem lower bounds from generalized BMM and OMv
Popular fine-grained hypotheses have been successful in proving conditional lower bounds
for many dynamic problems. Two of the most widely applicable hypotheses in this context …
for many dynamic problems. Two of the most widely applicable hypotheses in this context …
Deterministic fully dynamic sssp and more
J Van Den Brand, A Karczmarz - 2023 IEEE 64th Annual …, 2023 - ieeexplore.ieee.org
We present the first non-trivial fully dynamic algorithm maintaining exact single-source
distances in unweighted graphs. This resolves an open problem stated by Sankowski …
distances in unweighted graphs. This resolves an open problem stated by Sankowski …
Fast deterministic fully dynamic distance approximation
J Van Den Brand, S Forster… - 2022 IEEE 63rd Annual …, 2022 - ieeexplore.ieee.org
In this paper, we develop deterministic fully dynamic algorithms for computing approximate
distances in a graph with worst-case update time guarantees. In particular, we obtain …
distances in a graph with worst-case update time guarantees. In particular, we obtain …
Approximation algorithms and hardness for n-pairs shortest paths and all-nodes shortest cycles
We study the approximability of two related problems on graphs with n nodes and m edges:
n-Pairs Shortest Paths (n-PSP), where the goal is to find a shortest path between O (n) …
n-Pairs Shortest Paths (n-PSP), where the goal is to find a shortest path between O (n) …
Tight conditional lower bounds for approximating diameter in directed graphs
M Dalirrooyfard, N Wein - Proceedings of the 53rd Annual ACM SIGACT …, 2021 - dl.acm.org
Among the most fundamental graph parameters is the Diameter, the largest distance
between any pair of vertices in a graph. Computing the Diameter of a graph with m edges …
between any pair of vertices in a graph. Computing the Diameter of a graph with m edges …