39 citations · 40 across the 4 of their papers we have counts for
4 papers
Dynamic Connectivity: Connecting to Networks and Geometry
Timothy M. Chan, Mihai Patrascu, Liam Roditty
Dynamic connectivity is a well-studied problem, but so far the most compelling progress has been confined to the edge-update model: maintain an understanding of connectivity in an…
Radix Sorting With No Extra Space
Gianni Franceschini, S. Muthukrishnan, Mihai Patrascu
It is well known that n integers in the range [1,n^c] can be sorted in O(n) time in the RAM model using radix sorting. More generally, integers in any range [1,U] can be sorted in…
On Dynamic Range Reporting in One Dimension
Christian Worm Mortensen, Rasmus Pagh, Mihai Patrascu
We consider the problem of maintaining a dynamic set of integers and answering queries of the form: report a point (equivalently, all points) in a given interval. Range searching i…
Logarithmic Lower Bounds in the Cell-Probe Model
Mihai Patrascu, Erik D. Demaine
We develop a new technique for proving cell-probe lower bounds on dynamic data structures. This technique enables us to prove an amortized randomized Omega(lg n) lower bound per op…