26 citations · 54 across the 9 of their papers we have counts for
Showing 2005Show all
2 papers · 1 filter
cs.DM2005★ 6 cited
Bidimensionality, Map Graphs, and Grid Minors
Erik D. Demaine, MohammadTaghi Hajiaghayi
In this paper we extend the theory of bidimensionality to two families of graphs that do not exclude fixed minors: map graphs and power graphs. In both cases we prove a polynomial…
cs.DS2005
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…