In the decremental single-source shortest paths problem, the goal is to maintain distances
from a fixed source s to every vertex v in an m-edge graph undergoing edge deletions. In …

We study the fully dynamic All-Pairs Shortest Paths (APSP) problem in undirected edge-
weighted graphs. Given an n-vertex graph G with non-negative edge lengths, that …

We study the decremental All-Pairs Shortest Paths (APSP) problem in undirected edge-
weighted graphs. The input to the problem is an undirected n-vertex m-edge graph G with …

Designing approximate all-pairs distance oracles in the fully dynamic setting is one of the
central problems in dynamic graph algorithms. Despite extensive research on this topic, the …

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 …

Dynamic all-pairs shortest paths is a well-studied problem in the field of dynamic graph
algorithms. More specifically, given a directed weighted graph G=(V, E, ω) on n vertices …

In this paper we give the first efficient algorithms for the k-center problem on dynamic graphs
undergoing edge updates. In this problem, the goal is to partition the input into k sets by …

This paper is about the problem of finding a shortest $ s $-$ t $ path using at most $ h $
edges in edge-weighted graphs. The Bellman--Ford algorithm solves this problem in $ O …

We provide the first deterministic data structure that given a weighted undirected graph
undergoing edge insertions, processes each update with polylogarithmic amortized update …

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 …