6 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 o…
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…
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+…
Near Optimal Dual Fault Tolerant Distance Oracle
Dipan Dey, Manoj Gupta
We present a dual fault-tolerant distance oracle for undirected and unweighted graphs. Given a set of two edges, as well as a source node and a destination node , our or…
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…
The Group Access Bounds for Binary Search Trees
Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak +2
The access lemma (Sleator and Tarjan, JACM 1985) is a property of binary search trees that implies interesting consequences such as static optimality, static finger, and working se…