9 citations · 13 across the 3 of their papers we have counts for
4 papers · 1 filter
Fully Dynamic -Approximate Matchings
Manoj Gupta, Richard Peng
We present the first data structures that maintain near optimal maximum cardinality and maximum weighted matchings on sparse graphs in sublinear time per update. Our main result is…
Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs
Abhash Anand, Surender Baswana, Manoj Gupta +1
We present a fully dynamic algorithm for maintaining approximate maximum weight matching in general weighted graphs. The algorithm maintains a matching whose weight is a…
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…
An O(log(n)) Fully Dynamic Algorithm for Maximum matching in a tree
Manoj Gupta, Ankit Sharma
In this paper, we have developed a fully-dynamic algorithm for maintaining cardinality of maximum-matching in a tree using the construction of top-trees. The time complexities are…