3 papers
cs.DS2026
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 o…
cs.DS2026
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…
cs.DS2025
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+…