26 citations · 54 across the 9 of their papers we have counts for
27 papers
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…
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…
Communication-Aware Processor Allocation for Supercomputers
Michael A. Bender, David P. Bunde, Erik D. Demaine +4
This paper gives processor-allocation algorithms for minimizing the average number of communication hops between the assigned processors for grid architectures, in the presence of…
Online Searching with Turn Cost
Erik D. Demaine, Sandor P. Fekete, Shmuel Gal
We consider the problem of searching for an object on a line at an unknown distance OPT from the original position of the searcher, in the presence of a cost of d for each time the…
Optimal Covering Tours with Turn Costs
Esther M. Arkin, Michael A. Bender, Erik D. Demaine +3
We give the first algorithmic study of a class of ``covering tour'' problems related to the geometric Traveling Salesman Problem: Find a polygonal tour for a cutter so that it swee…
Optimal Adaptive Algorithms for Finding the Nearest and Farthest Point on a Parametric Black-Box Curve
Ilya Baran, Erik D. Demaine
We consider a general model for representing and manipulating parametric curves, in which a curve is specified by a black box mapping a parameter value between 0 and 1 to a point i…