16 citations · 17 across the 3 of their papers we have counts for
5 papers · 1 filter
Faster Deterministic All Pairs Shortest Paths in Congest Model
Udit Agarwal, Vijaya Ramachandran
We present a new deterministic algorithm for distributed weighted all pairs shortest paths (APSP) in both undirected and directed graphs. Our algorithm runs in …
A Polynomial Time Algorithm for Almost Optimal Vertex Fault Tolerant Spanners
Udit Agarwal
We present the first polynomial time algorithm for the f vertex fault tolerant spanner problem, which achieves almost optimal spanner size. Our algorithm for constructing f vertex…
New and Simplified Distributed Algorithms for Weighted All Pairs Shortest Paths
Udit Agarwal, Vijaya Ramachandran
We consider the problem of computing all pairs shortest paths (APSP) and shortest paths for k sources in a weighted graph in the distributed CONGEST model. For graphs with non-nega…
A Deterministic Distributed Algorithm for Weighted All Pairs Shortest Paths Through Pipelining
Udit Agarwal, Vijaya Ramachandran
We present a new pipelined approach to compute all pairs shortest paths (APSP) in a directed graph with nonnegative integer edge weights (including zero weights) in the CONGEST mod…
A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in Rounds
Udit Agarwal, Vijaya Ramachandran, Valerie King +1
We present a deterministic distributed algorithm to compute all-pairs shortest paths(APSP) in an edge-weighted directed or undirected graph. Our algorithm runs in $\tilde{O}(n^{3/2…