18 citations · 45 across the 11 of their papers we have counts for
Showing 2011Show all
3 papers · 1 filter
cs.DS2011★ 3 cited
The update complexity of selection and related problems
Manoj Gupta, Yogish Sabharwal, Sandeep Sen
We present a framework for computing with input data specified by intervals, representing uncertainty in the values of the input parameters. To compute a solution, the algorithm ca…
cs.DS2011★ 3 cited
Fully dynamic maximal matching in O(log n) update time
Surender Baswana, Manoj Gupta, Sandeep Sen
We present an algorithm for maintaining maximal matching in a graph under addition and deletion of edges. Our data structure is randomized that takes O(log n) expected amortized ti…
cs.DS2011
On Dynamic Optimality for Binary Search Trees
Navin Goyal, Manoj Gupta
Does there exist O(1)-competitive (self-adjusting) binary search tree (BST) algorithms? This is a well-studied problem. A simple offline BST algorithm GreedyFuture was proposed ind…