10 citations · 13 across the 8 of their papers we have counts for
Showing 2017Show all
2 papers · 1 filter
cs.DS2017★ 1 cited
Fine-Grained I/O Complexity via Reductions: New lower bounds, faster algorithms, and a time hierarchy
Erik D. Demaine, Andrea Lincoln, Quanquan C. Liu +2
This paper initiates the study of I/O algorithms (minimizing cache misses) from the perspective of fine-grained complexity (conditional polynomial lower bounds). Specifically, we a…
cs.CG2017
Upward Partitioned Book Embeddings
Hugo A. Akitaya, Erik D. Demaine, Adam Hesterberg +1
We analyze a directed variation of the book embedding problem when the page partition is prespecified and the nodes on the spine must be in topological order (upward book embedding…