This paper presents near-optimal deterministic parallel and distributed algorithms for
computing (1+ eps)-approximate single-source shortest paths in any undirected weighted …

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 present a (1+ ε)-approximate parallel algorithm for computing shortest paths in
undirected graphs, achieving poly (log n) depth and m poly (log n) work for n-nodes m …

We present a deterministic (1+ o (1))-approximation O (n 1/2+ o (1)+ D 1+ o (1))-time
algorithm for solving the single-source shortest paths problem on distributed weighted …

The distributed single-source shortest paths problem is one of the most fundamental and
central problems in the message-passing distributed computing. Classical Bellman-Ford …

We devise new algorithms for the single-source shortest paths (SSSP) problem with non-
negative edge weights in the CONGEST model of distributed computing. While close-to …

Spanners, emulators, and approximate distance oracles can be viewed as lossy
compression schemes that represent an unweighted graph metric in small space, say …

We present a method for solving the transshipment problem-also known as uncapacitated
minimum cost flow-up to a multiplicative error of $1+\varepsilon $ in undirected graphs with …

Miller et al.[48] devised a distributed1 algorithm in the CONGEST model that, given a
parameter k= 1, 2,…, constructs an O (k)-spanner of an input unweighted n-vertex graph with …

Hopsets and spanners are fundamental graph structures, playing a key role in shortest path
computation, distributed communication, and more. A (near-exact) hopset for a given graph …