26 citations · 145 across the 52 of their papers we have counts for
5 papers · 1 filter
2-Colorable Perfect Matching is NP-complete in 2-Connected 3-Regular Planar Graphs
Erik D. Demaine, Kritkorn Karntikoon, Nipun Pitimanaaree
The 2-colorable perfect matching problem asks whether a graph can be colored with two colors so that each node has exactly one neighbor with the same color as itself. We prove that…
When Can You Tile an Integer Rectangle with Integer Squares?
MIT CompGeom Group, Zachary Abel, Hugo A. Akitaya +3
This paper characterizes when an rectangle, where and are integers, can be tiled (exactly packed) by squares where each has an integer side length of at least…
Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines
Hayashi Ani, Michael Coulombe, Erik D. Demaine +4
We extend the motion-planning-through-gadgets framework to several new scenarios involving various numbers of robots/agents, and analyze the complexity of the resulting motion-plan…
Complexity of Simple Folding of Mixed Orthogonal Crease Patterns
Hugo Akitaya, Josh Brunner, Erik D. Demaine +3
Continuing results from JCDCGGG 2016 and 2017, we solve several new cases of the simple foldability problem -- deciding which crease patterns can be folded flat by a sequence of (s…
Every Author as First Author
Erik D. Demaine, Martin L. Demaine
We propose a new standard for writing author names on papers and in bibliographies, which places every author as a first author -- superimposed. This approach enables authors to wr…