18 citations · 45 across the 11 of their papers we have counts for
15 papers · 1 filter
Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition
Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak +3
Greedy BST (or simply Greedy) is an online self-adjusting binary search tree defined in the geometric view ([Lucas, 1988; Munro, 2000; Demaine, Harmon, Iacono, Kane, Patrascu, SODA…
Near Optimal Algorithm for Fault Tolerant Distance Oracle and Single Source Replacement Path problem
Dipan Dey, Manoj Gupta
In a graph with a source , we design a distance oracle that can answer the following query: Query -- find the length of shortest path from a fixed source to any…
Multiple Source Replacement Path Problem
Manoj Gupta, Rahul Jain, Nitiksha Modi
One of the classical line of work in graph algorithms has been the Replacement Path Problem: given a graph , and , find shortest paths from to avoiding each edge…
Nearly Optimal Space Efficient Algorithm for Depth First Search
Jayesh Choudhari, Manoj Gupta, Shivdutt Sharma
We design a space-efficient algorithm for performing depth-first search traversal(DFS) of a graph in time using bits of space. While a normal DFS algorithm…
Generic Single Edge Fault Tolerant Exact Distance Oracle
Manoj Gupta, Aditi Singh
Given an undirected unweighted graph and a source set of sources, we want to build a data structure which can process the following query {\sc Q} find t…
Simple dynamic algorithms for Maximal Independent Set and other problems
Manoj Gupta, Shahbaz Khan
Most graphs in real life keep changing with time. These changes can be in the form of insertion or deletion of edges or vertices. Such rapidly changing graphs motivate us to study…