4 papers
ptimal Algorithm for 2-Approximate All Pair Shortest Paths -- almost
Manoj Gupta, Mrigankashekhar Shandilya
Given an undirected, unweighted graph , we aim to compute a 2-approximation of all-pairs shortest paths (APSP). This problem admits a natural lower bound of since the…
Approximate Single Source Dual Fault Tolerant Distance Oracle
Koustav Das, Manoj Gupta
We are given an undirected weighted graph with vertices and edges, edge weights in , and a designated source vertex . We design a single source dual fault to…
Nearly Optimal Fault Tolerant Distance Oracle
Dipan Dey, Manoj Gupta
We present an -fault tolerant distance oracle for an undirected weighted graph where each edge has an integral weight from . Given a set of edges, as well a…
Improved 2-Approximate Shortest Paths for close vertex pairs
Manoj Gupta
An influential result by Dor, Halperin, and Zwick (FOCS 1996, SICOMP 2000) implies an algorithm that can compute approximate shortest paths for all vertex pairs in $\tilde{O}(n^{2+…