default search action
Erik D. Demaine
Person information
- affiliation: MIT, Cambridge, US
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
- [c346]Erik D. Demaine, Timothy Gomez, Elise Grizzell, Markus Hecher, Jayson Lynch, Robert T. Schweller, Ahmed Shalaby, Damien Woods:
Domain-Based Nucleic-Acid Minimum Free Energy: Algorithmic Hardness and Parameterized Bounds. DNA 2024: 2:1-2:24 - [c345]MIT Hardness Group, Hayashi Ani, Erik D. Demaine, Holden Hall, Matias Korman:
PSPACE-Hard 2D Super Mario Games: Thirteen Doors. FUN 2024: 21:1-21:19 - [c344]MIT Hardness Group, Hayashi Ani, Erik D. Demaine, Holden Hall, Ricardo Ruiz, Naveen Venkat:
You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games. FUN 2024: 22:1-22:20 - [c343]MIT Hardness Group, Josh Brunner, Lily Chung, Erik D. Demaine, Della H. Hendrickson, Andy Tockman:
ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles. FUN 2024: 23:1-23:20 - [c342]MIT Hardness Group, Erik D. Demaine, Holden Hall, Jeffery Li:
Tetris with Few Piece Types. FUN 2024: 24:1-24:18 - [c341]Erik D. Demaine, Yael Kirkpatrick, Rebecca Lin:
Graph Threading. ITCS 2024: 38:1-38:18 - [c340]Hugo A. Akitaya, Ahmad Biniaz, Erik D. Demaine, Linda Kleist, Frederick Stock, Csaba D. Tóth:
Minimum Plane Bichromatic Spanning Trees. ISAAC 2024: 4:1-4:14 - [c339]MIT Hardness Group, Josh Brunner, Erik D. Demaine, Jenny Diomidova, Timothy Gomez, Markus Hecher, Frederick Stock, Zixiang Zhou:
Easier Ways to Prove Counting Hard: A Dichotomy for Generalized #SAT, Applied to Constraint Graphs. ISAAC 2024: 51:1-51:14 - [c338]Rebecca Lin, Wenzhong Yan, Ankur Mehta, Erik D. Demaine:
Routing Reconfigurations. SCF Adjunct 2024: 14:1-14:3 - [c337]MIT-NASA Space Robots Team, Josh Brunner, Kenneth C. Cheung, Erik D. Demaine, Jenny Diomidova, Christine Gregg, Della H. Hendrickson, Irina Kostitsyna:
Reconfiguration Algorithms for Cubic Modular Robots with Realistic Movement Constraints. SWAT 2024: 34:1-34:18 - [c336]Hayashi Ani, Josh Brunner, Erik D. Demaine, Jenny Diomidova, Timothy Gomez, Della H. Hendrickson, Yael Kirkpatrick, Jeffery Li, Jayson Lynch, Ritam Nag, Frederick Stock:
Agent Motion Planning as Block Asynchronous Cellular Automata: Pushing, Pulling, Suplexing, and More. UCNC 2024: 219-236 - [i201]MIT CompGeom Group, Hugo A. Akitaya, Erik D. Demaine, Adam Hesterberg, Anna Lubiw, Jayson Lynch, Joseph O'Rourke, Frederick Stock:
Super Guarding and Dark Rays in Art Galleries. CoRR abs/2404.04613 (2024) - [i200]MIT Hardness Group, Hayashi Ani, Erik D. Demaine, Holden Hall, Matias Korman:
PSPACE-Hard 2D Super Mario Games: Thirteen Doors. CoRR abs/2404.10380 (2024) - [i199]MIT Hardness Group, Erik D. Demaine, Holden Hall, Jeffery Li:
Tetris with Few Piece Types. CoRR abs/2404.10712 (2024) - [i198]MIT Hardness Group, Josh Brunner, Della H. Hendrickson, Lily Chung, Erik D. Demaine, Andy Tockman:
ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles. CoRR abs/2405.08377 (2024) - [i197]MIT Hardness Group, Hayashi Ani, Erik D. Demaine, Holden Hall, Ricardo Ruiz, Naveen Venkat:
You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games. CoRR abs/2405.10546 (2024) - [i196]MIT-NASA Space Robots Team, Josh Brunner, Kenneth C. Cheung, Erik D. Demaine, Jenny Diomidova, Christine Gregg, Della H. Hendrickson, Irina Kostitsyna:
Reconfiguration Algorithms for Cubic Modular Robots with Realistic Movement Constraints. CoRR abs/2405.15724 (2024) - [i195]Erik D. Demaine, Yael Kirkpatrick, Rebecca Lin:
Graph Threading with Turn Costs. CoRR abs/2405.17953 (2024) - [i194]MIT Hardness Group, Nithid Anchaleenukoon, Alex Dang, Erik D. Demaine, Kaylee Ji, Pitchayut Saengrungkongka:
Complexity of 2D Snake Cube Puzzles. CoRR abs/2407.10323 (2024) - [i193]Erik D. Demaine, Stefan Langerman:
Tiling with Three Polygons is Undecidable. CoRR abs/2409.11582 (2024) - [i192]Hugo A. Akitaya, Ahmad Biniaz, Erik D. Demaine, Linda Kleist, Frederick Stock, Csaba D. Tóth:
Minimum Plane Bichromatic Spanning Trees. CoRR abs/2409.11614 (2024) - 2023
- [j205]Joshua Ani, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, Jayson Lynch:
Traversability, Reconfiguration, and Reachability in the Gadget Framework. Algorithmica 85(11): 3453-3486 (2023) - [j204]Erik D. Demaine, Martin L. Demaine, Ryuhei Uehara:
Developing a tetramonohedron with minimum cut length. Comput. Geom. 108: 101903 (2023) - [j203]Erik D. Demaine, Maarten Löffler, Christiane Schmidt:
Rectangular Spiral Galaxies are still hard. Comput. Geom. 110: 101949 (2023) - [j202]Erik D. Demaine, Martin L. Demaine, Yevhenii Diomidov, Tonan Kamata, Ryuhei Uehara, Hanyu Alice Zhang:
Any platonic solid can transform to another by O(1) refoldings. Comput. Geom. 113: 101995 (2023) - [j201]Joshua Ani, Erik D. Demaine, Dylan H. Hendrickson, Jayson Lynch:
Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets. Theor. Comput. Sci. 969: 113945 (2023) - [c335]Joseph O'Rourke, Hugo A. Akitaya, Erik D. Demaine, Adam Hesterberg, Anna Lubiw, Jayson Lynch, Frederick Stock:
Super Guarding and Dark Rays in Art Galleries. CCCG 2023: 51-61 - [c334]Robert M. Alaniz, Michael J. Coulombe, Erik D. Demaine, Bin Fu, Ryan Knobel, Timothy Gomez, Elise Grizzell, Andrew Rodriguez, Robert T. Schweller, Tim Wylie:
Reconfiguration of Linear Surface Chemical Reaction Networks with Bounded State Change. CCCG 2023: 265-271 - [c333]Robert M. Alaniz, Josh Brunner, Michael J. Coulombe, Erik D. Demaine, Jenny Diomidova, Timothy Gomez, Elise Grizzell, Ryan Knobel, Jayson Lynch, Andrew Rodriguez, Robert T. Schweller, Tim Wylie:
Complexity of Reconfiguration in Surface Chemical Reaction Networks. DNA 2023: 10:1-10:18 - [c332]Joshua Ani, Michael J. Coulombe, Erik D. Demaine, Yevhenii Diomidov, Timothy Gomez, Dylan H. Hendrickson, Jayson Lynch:
Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines. SAND 2023: 5:1-5:21 - [i191]Aviv Adler, Joshua Ani, Lily Chung, Michael J. Coulombe, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, Jayson Lynch:
This Game Is Not Going To Analyze Itself. CoRR abs/2302.01145 (2023) - [i190]Josh Brunner, Lily Chung, Michael J. Coulombe, Erik D. Demaine, Timothy Gomez, Jayson Lynch:
Complexity of Solo Chess with Unlimited Moves. CoRR abs/2302.01405 (2023) - [i189]Robert M. Alaniz, Josh Brunner, Michael J. Coulombe, Erik D. Demaine, Yevhenii Diomidov, Ryan Knobel, Timothy Gomez, Elise Grizzell, Jayson Lynch, Andrew Rodriguez, Robert T. Schweller, Tim Wylie:
Complexity of Reconfiguration in Surface Chemical Reaction Networks. CoRR abs/2303.15556 (2023) - [i188]Erik D. Demaine, Martin L. Demaine:
Every Author as First Author. CoRR abs/2304.01393 (2023) - [i187]Hugo A. Akitaya, Josh Brunner, Erik D. Demaine, Dylan H. Hendrickson, Victor Luo, Andy Tockman:
Complexity of Simple Folding of Mixed Orthogonal Crease Patterns. CoRR abs/2306.00702 (2023) - [i186]Joshua Ani, Michael J. Coulombe, Erik D. Demaine, Yevhenii Diomidov, Timothy Gomez, Dylan H. Hendrickson, Jayson Lynch:
Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines. CoRR abs/2306.01193 (2023) - [i185]MIT CompGeom Group, Zachary Abel, Hugo A. Akitaya, Erik D. Demaine, Adam C. Hesterberg, Jayson Lynch:
When Can You Tile an Integer Rectangle with Integer Squares? CoRR abs/2308.15317 (2023) - [i184]Erik D. Demaine, Kritkorn Karntikoon, Nipun Pitimanaaree:
2-Colorable Perfect Matching is NP-complete in 2-Connected 3-Regular Planar Graphs. CoRR abs/2309.09786 (2023) - [i183]Erik D. Demaine, Yael Kirkpatrick, Rebecca Lin:
Graph Threading. CoRR abs/2309.10122 (2023) - 2022
- [j200]Hugo A. Akitaya, Erik D. Demaine, David Eppstein, Tomohiro Tachi, Ryuhei Uehara:
Ununfoldable polyhedra with 6 vertices or 6 faces. Comput. Geom. 103: 101857 (2022) - [j199]Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, Joseph S. B. Mitchell:
Area-Optimal Simple Polygonalizations: The CG Challenge 2019. ACM J. Exp. Algorithmics 27: 2.4:1-2.4:12 (2022) - [c331]Elena Arseneva, Erik D. Demaine, Tonan Kamata, Ryuhei Uehara:
Discretization to Prove the Nonexistence of "Small" Common Unfoldings Between Polyhedra. CCCG 2022: 9-23 - [c330]Erik D. Demaine, Hiro Ito, Jayson Lynch, Ryuhei Uehara:
Computational Complexity of Flattening Fixed-Angle Orthogonal Chains. CCCG 2022: 98-104 - [c329]Sagnik Saha, Erik D. Demaine:
ZHED is NP-complete. CCCG 2022: 277-283 - [c328]Lily Chung, Erik D. Demaine, Dylan H. Hendrickson, Victor Luo:
Flat Folding an Unassigned Single-Vertex Complex (Combinatorially Embedded Planar Graph with Specified Edge Lengths) Without Flat Angles. SoCG 2022: 29:1-29:17 - [c327]Oswin Aichholzer, Erik D. Demaine, Matias Korman, Anna Lubiw, Jayson Lynch, Zuzana Masárová, Mikhail Rudoy, Virginia Vassilevska Williams, Nicole Wein:
Hardness of Token Swapping on Trees. ESA 2022: 3:1-3:15 - [c326]Joshua Ani, Lily Chung, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, Jayson Lynch:
Pushing Blocks via Checkable Gadgets: PSPACE-Completeness of Push-1F and Block/Box Dude. FUN 2022: 3:1-3:30 - [c325]Akira Baes, Erik D. Demaine, Martin L. Demaine, Elizabeth Hartung, Stefan Langerman, Joseph O'Rourke, Ryuhei Uehara, Yushi Uno, Aaron Williams:
Rolling Polyhedra on Tessellations. FUN 2022: 6:1-6:16 - [c324]Lily Chung, Erik D. Demaine, Dylan H. Hendrickson, Jayson Lynch:
Lower Bounds on Retroactive Data Structures. ISAAC 2022: 32:1-32:12 - [c323]Erik D. Demaine, Robert A. Hearn, Dylan H. Hendrickson, Jayson Lynch:
PSPACE-Completeness of Reversible Deterministic Systems. MCU 2022: 91-108 - [c322]Hugo A. Akitaya, Erik D. Demaine, Matias Korman, Irina Kostitsyna, Irene Parada, Willem Sonke, Bettina Speckmann, Ryuhei Uehara, Jules Wulms:
Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares. SWAT 2022: 4:1-4:19 - [c321]Joshua Ani, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, Jayson Lynch:
Traversability, Reconfiguration, and Reachability in the Gadget Framework. WALCOM 2022: 47-58 - [c320]Joshua Ani, Erik D. Demaine, Dylan H. Hendrickson, Jayson Lynch:
Trains, Games, and Complexity: 0/1/2-Player Motion Planning Through Input/Output Gadgets. WALCOM 2022: 187-198 - [i182]Erik D. Demaine, Kritkorn Karntikoon:
Unfolding Orthotubes with a Dual Hamiltonian Path. CoRR abs/2201.12452 (2022) - [i181]Joshua Ani, Josh Brunner, Erik D. Demaine, Martin L. Demaine, Dylan H. Hendrickson, Victor Luo, Rachana Madhukara:
Orthogonal Fold & Cut. CoRR abs/2202.01293 (2022) - [i180]Jeffrey Bosboom, Josh Brunner, Michael J. Coulombe, Erik D. Demaine, Dylan H. Hendrickson, Jayson Lynch, Elle Najt:
The Legend of Zelda: The Complexity of Mechanics. CoRR abs/2203.17167 (2022) - [i179]Joshua Ani, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, Jayson Lynch:
Traversability, Reconfiguration, and Reachability in the Gadget Framework. CoRR abs/2204.00600 (2022) - [i178]Lily Chung, Erik D. Demaine, Dylan H. Hendrickson, Victor Luo:
Flat Folding an Unassigned Single-Vertex Complex (Combinatorially Embedded Planar Graph with Specified Edge Lengths) without Flat Angles. CoRR abs/2204.03696 (2022) - [i177]Oswin Aichholzer, Brad Ballinger, Therese Biedl, Mirela Damian, Erik D. Demaine, Matias Korman, Anna Lubiw, Jayson Lynch, Josef Tkadlec, Yushi Uno:
Reconfiguration of Non-crossing Spanning Trees. CoRR abs/2206.03879 (2022) - [i176]Erik D. Demaine, Robert A. Hearn, Dylan H. Hendrickson, Jayson Lynch:
PSPACE-Completeness of Reversible Deterministic Systems. CoRR abs/2207.07229 (2022) - [i175]Lily Chung, Erik D. Demaine:
Celeste is PSPACE-hard. CoRR abs/2211.11839 (2022) - [i174]Lily Chung, Erik D. Demaine, Dylan H. Hendrickson, Jayson Lynch:
Lower Bounds on Retroactive Data Structures. CoRR abs/2211.14664 (2022) - [i173]Erik D. Demaine, Hiro Ito, Jayson Lynch, Ryuhei Uehara:
Computational Complexity of Flattening Fixed-Angle Orthogonal Chains. CoRR abs/2212.12450 (2022) - 2021
- [j198]Hugo A. Akitaya, Esther M. Arkin, Mirela Damian, Erik D. Demaine, Vida Dujmovic, Robin Y. Flatland, Matias Korman, Belén Palop, Irene Parada, André van Renssen, Vera Sacristán:
Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers. Algorithmica 83(5): 1316-1351 (2021) - [j197]Erik D. Demaine, Yamming Huang, Chung-Shou Liao, Kunihiko Sadakane:
Approximating the Canadian Traveller Problem with Online Randomization. Algorithmica 83(5): 1524-1543 (2021) - [j196]Oswin Aichholzer, Hugo A. Akitaya, Kenneth C. Cheung, Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Linda Kleist, Irina Kostitsyna, Maarten Löffler, Zuzana Masárová, Klara Mundilova, Christiane Schmidt:
Folding polyominoes with holes into a cube. Comput. Geom. 93: 101700 (2021) - [j195]Zachary Abel, Erik D. Demaine, Martin L. Demaine, Jason S. Ku, Jayson Lynch, Jin-ichi Itoh, Chie Nara:
Continuous flattening of all polyhedral manifolds using countably infinite creases. Comput. Geom. 98: 101773 (2021) - [j194]Zachary Abel, Hugo A. Akitaya, Man-Kwun Chiu, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Matias Korman, Jayson Lynch, André van Renssen, Marcel Roeloffzen:
Snipperclips: Cutting tools into desired polygons using themselves. Comput. Geom. 98: 101784 (2021) - [j193]Erik D. Demaine, John Iacono, Grigorios Koumoutsos, Stefan Langerman:
Belga B-Trees. Theory Comput. Syst. 65(3): 541-558 (2021) - [j192]Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, David Furcy, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, Andrew Winslow:
On the effects of hierarchical self-assembly for reducing program-size complexity. Theor. Comput. Sci. 894: 50-78 (2021) - [c319]Fotini Christia, Michael J. Curry, Constantinos Daskalakis, Erik D. Demaine, John P. Dickerson, MohammadTaghi Hajiaghayi, Adam Hesterberg, Marina Knittel, Aidan Milliff:
Scalable Equilibrium Computation in Multi-agent Influence Games on Networks. AAAI 2021: 5277-5285 - [c318]Erik D. Demaine, Jayson Lynch, Mikhail Rudoy, Yushi Uno:
Yin-Yang Puzzles are NP-complete. CCCG 2021: 97-106 - [c317]Hugo A. Akitaya, Brad Ballinger, Erik D. Demaine, Thomas C. Hull, Christiane Schmidt:
Folding Points to a Point and Lines to a Line. CCCG 2021: 271-278 - [c316]Erik D. Demaine, Martin L. Demaine, Yevhenii Diomidov, Tonan Kamata, Ryuhei Uehara, Hanyu Alice Zhang:
Any Regular Polyhedron Can Transform to Another by O(1) Refoldings. CCCG 2021: 332-342 - [c315]Vincent Bian, Erik D. Demaine, Rachana Madhukara:
Edge-Unfolding Prismatoids: Tall or Rectangular Base. CCCG 2021: 343-347 - [c314]Hugo A. Akitaya, Erik D. Demaine, Andrei Gonczi, Dylan H. Hendrickson, Adam Hesterberg, Matias Korman, Oliver Korten, Jayson Lynch, Irene Parada, Vera Sacristán:
Characterizing Universal Reconfigurability of Modular Pivoting Robots. SoCG 2021: 10:1-10:20 - [c313]Aviv Adler, Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Quanquan C. Liu, Jayson Lynch:
Tatamibari Is NP-Complete. FUN 2021: 1:1-1:24 - [c312]Joshua Ani, Jeffrey Bosboom, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, Jayson Lynch:
Walking Through Doors Is Hard, Even Without Staircases: Proving PSPACE-Hardness via Planar Assemblies of Door Gadgets. FUN 2021: 3:1-3:23 - [c311]Josh Brunner, Lily Chung, Erik D. Demaine, Dylan H. Hendrickson, Adam Hesterberg, Adam Suhl, Avi Zeff:
1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete. FUN 2021: 7:1-7:14 - [c310]Erik D. Demaine, Adam Hesterberg, Frederic Koehler, Jayson Lynch, John C. Urschel:
Multidimensional Scaling: Approximation and Complexity. ICML 2021: 2568-2578 - [c309]Erik D. Demaine, Jayson Lynch, Jiaying Sun:
An Efficient Reversible Algorithm for Linear Regression. ICRC 2021: 103-108 - [i172]Erik D. Demaine, Yevhenii Diomidov:
Strings-and-Coins and Nimstring are PSPACE-complete. CoRR abs/2101.06361 (2021) - [i171]Oswin Aichholzer, Erik D. Demaine, Matias Korman, Jayson Lynch, Anna Lubiw, Zuzana Masárová, Mikhail Rudoy, Virginia Vassilevska Williams, Nicole Wein:
Hardness of Token Swapping on Trees. CoRR abs/2103.06707 (2021) - [i170]Zachary Abel, Hugo A. Akitaya, Man-Kwun Chiu, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Matias Korman, Jayson Lynch, André van Renssen, Marcel Roeloffzen:
Snipperclips: Cutting Tools into Desired Polygons using Themselves. CoRR abs/2105.08305 (2021) - [i169]Zachary Abel, Erik D. Demaine, Martin L. Demaine, Jason S. Ku, Jayson Lynch, Jin-ichi Itoh, Chie Nara:
Continuous Flattening of All Polyhedral Manifolds using Countably Infinite Creases. CoRR abs/2105.10774 (2021) - [i168]Vincent Bian, Erik D. Demaine, Rachana Madhukara:
Edge-Unfolding Prismatoids: Tall or Rectangular Base. CoRR abs/2106.14262 (2021) - [i167]Erik D. Demaine, Jayson Lynch, Mikhail Rudoy, Yushi Uno:
Yin-Yang Puzzles are NP-complete. CoRR abs/2106.15585 (2021) - [i166]Erik D. Demaine, Martin L. Demaine, Yevhenii Diomidov, Tonan Kamata, Ryuhei Uehara, Hanyu Alice Zhang:
Any Regular Polyhedron Can Transform to Another by O(1) Refoldings. CoRR abs/2109.03997 (2021) - [i165]Erik D. Demaine, Adam Hesterberg, Frederic Koehler, Jayson Lynch, John C. Urschel:
Multidimensional Scaling: Approximation and Complexity. CoRR abs/2109.11505 (2021) - [i164]Erik D. Demaine, Maarten Löffler, Christiane Schmidt:
Rectangular Spiral Galaxies are Still Hard. CoRR abs/2110.00058 (2021) - [i163]Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, Joseph S. B. Mitchell:
Area-Optimal Simple Polygonalizations: The CG Challenge 2019. CoRR abs/2111.07304 (2021) - [i162]Sagnik Saha, Erik D. Demaine:
ZHED is NP-complete. CoRR abs/2112.07914 (2021) - 2020
- [j191]Molly Baird, Sara C. Billey, Erik D. Demaine, Martin L. Demaine, David Eppstein, Sándor P. Fekete, Graham Gordon, Sean Griffin, Joseph S. B. Mitchell, Joshua P. Swanson:
Existence and Hardness of Conveyor Belts. Electron. J. Comb. 27(4): 4 (2020) - [j190]Nadia M. Benbernou, Erik D. Demaine, Martin L. Demaine, Anna Lubiw:
Universal hinge patterns for folding strips efficiently into any grid polyhedron. Comput. Geom. 89: 101633 (2020) - [j189]Erik D. Demaine, Matias Korman, Jason S. Ku, Joseph S. B. Mitchell, Yota Otachi, André van Renssen, Marcel Roeloffzen, Ryuhei Uehara, Yushi Uno:
Symmetric assembly puzzles are hard, beyond a few pieces. Comput. Geom. 90: 101648 (2020) - [j188]Jin Akiyama, Erik D. Demaine, Stefan Langerman:
Polyhedral Characterization of Reversible Hinged Dissections. Graphs Comb. 36(2): 221-229 (2020) - [j187]Hugo A. Akitaya, Cordelia Avery, Joseph Bergeron, Erik D. Demaine, Justin Kopinsky, Jason S. Ku:
Infinite All-Layers Simple Foldability. Graphs Comb. 36(2): 231-244 (2020) - [j186]Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Roderick Kimball, Justin Kopinsky:
Path Puzzles: Discrete Tomography with a Path Constraint is Hard. Graphs Comb. 36(2): 251-267 (2020) - [j185]Erik D. Demaine, Hiro Ito, Stefan Langerman, Jayson Lynch, Mikhail Rudoy, Kai Xiao:
Cookie Clicker. Graphs Comb. 36(2): 269-302 (2020) - [j184]Erik D. Demaine, Martin L. Demaine:
Adventures in Maze Folding Art. J. Inf. Process. 28: 745-749 (2020) - [j183]Erik D. Demaine, Martin L. Demaine, Hiro Ito, Chie Nara, Izumi Shirahama, Tomohiro Tachi, Mizuho Tomura:
Flat Folding a Strip with Parallel or Nonacute Zigzag Creases with Mountain-Valley Assignment. J. Inf. Process. 28: 825-833 (2020) - [j182]Joshua Ani, Sualeh Asif, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, Jayson Lynch, Sarah Scheffler, Adam Suhl:
PSPACE-completeness of Pulling Blocks to Reach a Goal. J. Inf. Process. 28: 929-941 (2020) - [j181]Sualeh Asif, Michael J. Coulombe, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Jayson Lynch, Mihir Singhal:
Tetris is NP-hard even with O(1) Rows or Columns. J. Inf. Process. 28: 942-958 (2020) - [j180]Jeffrey Bosboom, Charlotte Chen, Lily Chung, Spencer Compton, Michael J. Coulombe, Erik D. Demaine, Martin L. Demaine, Ivan Tadeu Ferreira Antunes Filho, Dylan H. Hendrickson, Adam Hesterberg, Calvin Hsu, William Hu, Oliver Korten, Zhezheng Luo, Lillian Zhang:
Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players. J. Inf. Process. 28: 987-1007 (2020) - [j179]Hugo A. Akitaya, Erik D. Demaine, Takashi Horiyama, Thomas C. Hull, Jason S. Ku, Tomohiro Tachi:
Rigid foldability is NP-hard. J. Comput. Geom. 11(1): 93-124 (2020) - [j178]Jean Cardinal, Erik D. Demaine, David Eppstein, Robert A. Hearn, Andrew Winslow:
Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect. Theor. Comput. Sci. 806: 332-343 (2020) - [j177]Zachary Abel, Jeffrey Bosboom, Michael J. Coulombe, Erik D. Demaine, Linus Hamilton, Adam Hesterberg, Justin Kopinsky, Jayson Lynch, Mikhail Rudoy, Clemens Thielen:
Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible. Theor. Comput. Sci. 839: 41-102 (2020) - [c308]Erik D. Demaine:
Tribute to Godfried Toussaint. CCCG 2020: 1 - [c307]Man-Kwun Chiu, Erik D. Demaine, Yevhenii Diomidov, David Eppstein, Robert A. Hearn, Adam Hesterberg, Matias Korman, Irene Parada, Mikhail Rudoy:
New Results in Sona Drawing: Hardness and TSP Separation. CCCG 2020: 63-72 - [c306]Kingston Yao Czajkowski, Erik D. Demaine, Martin L. Demaine, Kim Eppling, Robby Kraft, Klara Mundilova, Levi Smith:
Folding Small Polyominoes into a Unit Cube. CCCG 2020: 95-100 - [c305]Erik D. Demaine, Martin L. Demaine, David Eppstein, Joseph O'Rourke:
Some Polycubes Have No Edge Zipper Unfolding. CCCG 2020: 101-105 - [c304]Erik D. Demaine, Martin L. Demaine, David Eppstein:
Acutely Triangulated, Stacked, and Very Ununfoldable Polyhedra. CCCG 2020: 106-113 - [c303]Hugo A. Akitaya, Erik D. Demaine, Jason S. Ku, Jayson Lynch, Csaba D. Tóth:
2048 Without Merging. CCCG 2020: 285-291 - [c302]Erik D. Demaine, Adam Hesterberg, Jason S. Ku:
Finding Closed Quasigeodesics on Convex Polyhedra. SoCG 2020: 33:1-33:13 - [c301]Erik D. Demaine, Dylan H. Hendrickson, Jayson Lynch:
Toward a General Complexity Theory of Motion Planning: Characterizing Which Gadgets Make Games Hard. ITCS 2020: 62:1-62:42 - [c300]Leo Alcock, Sualeh Asif, Jeffrey Bosboom, Josh Brunner, Charlotte Chen, Erik D. Demaine, Rogers Epstein, Adam Hesterberg, Lior Hirschfeld, William Hu, Jayson Lynch, Sarah Scheffler, Lillian Zhang:
Arithmetic Expression Construction. ISAAC 2020: 12:1-12:15 - [c299]Josh Brunner, Erik D. Demaine, Dylan H. Hendrickson, Julian Wellman:
Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess Is Hard. ISAAC 2020: 17:1-17:14 - [c298]Erik D. Demaine, Justin Kopinsky, Jayson Lynch:
Recursed Is Not Recursive: A Jarring Result. ISAAC 2020: 50:1-50:15 - [i161]Jeffrey Bosboom, Charlotte Chen, Lily Chung, Spencer Compton, Michael J. Coulombe, Erik D. Demaine, Martin L. Demaine, Ivan Tadeu Ferreira Antunes Filho, Dylan H. Hendrickson, Adam Hesterberg, Calvin Hsu, William Hu, Oliver Korten, Zhezheng Luo, Lillian Zhang:
Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players. CoRR abs/2002.03887 (2020) - [i160]Erik D. Demaine, Justin Kopinsky, Jayson Lynch:
Recursed is not Recursive: A Jarring Result. CoRR abs/2002.05131 (2020) - [i159]Aviv Adler, Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Quanquan C. Liu, Jayson Lynch:
Tatamibari is NP-complete. CoRR abs/2003.08331 (2020) - [i158]Josh Brunner, Lily Chung, Erik D. Demaine, Dylan H. Hendrickson, Adam Hesterberg, Adam Suhl, Avi Zeff:
1 x 1 Rush Hour with Fixed Blocks is PSPACE-complete. CoRR abs/2003.09914 (2020) - [i157]Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, Joseph S. B. Mitchell:
Computing Convex Partitions for Point Sets in the Plane: The CG: SHOP Challenge 2020. CoRR abs/2004.04207 (2020) - [i156]Joshua Ani, Erik D. Demaine, Dylan H. Hendrickson, Jayson Lynch:
Trains, Games, and Complexity: 0/1/2-Player Motion Planning through Input/Output Gadgets. CoRR abs/2005.03192 (2020) - [i155]Zachary Abel, Hugo A. Akitaya, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Matias Korman, Jason S. Ku, Jayson Lynch:
Negative Instance for the Edge Patrolling Beacon Problem. CoRR abs/2006.01202 (2020) - [i154]Joshua Ani, Jeffrey Bosboom, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, Jayson Lynch:
Walking through Doors is Hard, even without Staircases: Proving PSPACE-hardness via Planar Assemblies of Door Gadgets. CoRR abs/2006.01256 (2020) - [i153]Joshua Ani, Sualeh Asif, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, Jayson Lynch, Sarah Scheffler, Adam Suhl:
PSPACE-completeness of Pulling Blocks to Reach a Goal. CoRR abs/2006.04337 (2020) - [i152]Zachary Abel, Hugo A. Akitaya, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Jason S. Ku, Jayson Lynch:
Escaping a Polygon. CoRR abs/2007.08965 (2020) - [i151]Erik D. Demaine, Martin L. Demaine, David Eppstein:
Acutely Triangulated, Stacked, and Very Ununfoldable Polyhedra. CoRR abs/2007.14525 (2020) - [i150]Man-Kwun Chiu, Erik D. Demaine, Yevhenii Diomidov, David Eppstein, Robert A. Hearn, Adam Hesterberg, Matias Korman, Irene Parada, Mikhail Rudoy:
New Results in Sona Drawing: Hardness and TSP Separation. CoRR abs/2007.15784 (2020) - [i149]Erik D. Demaine, Adam C. Hesterberg, Jason S. Ku:
Finding Closed Quasigeodesics on Convex Polyhedra. CoRR abs/2008.00589 (2020) - [i148]Sualeh Asif, Michael J. Coulombe, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Jayson Lynch, Mihir Singhal:
Tetris is NP-hard even with $O(1)$ rows or columns. CoRR abs/2009.14336 (2020) - [i147]Josh Brunner, Erik D. Demaine, Dylan H. Hendrickson, Julian Wellman:
Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess is Hard. CoRR abs/2010.09271 (2020) - [i146]Leo Alcock, Sualeh Asif, Jeffrey Bosboom, Josh Brunner, Charlotte Chen, Erik D. Demaine, Rogers Epstein, Adam Hesterberg, Lior Hirschfeld, William Hu, Jayson Lynch, Sarah Scheffler, Lillian Zhang:
Arithmetic Expression Construction. CoRR abs/2011.11767 (2020) - [i145]Hugo A. Akitaya, Erik D. Demaine, Andrei Gonczi, Dylan H. Hendrickson, Adam Hesterberg, Matias Korman, Oliver Korten, Jayson Lynch, Irene Parada, Vera Sacristán:
Characterizing Universal Reconfigurability of Modular Pivoting Robots. CoRR abs/2012.07556 (2020)
2010 – 2019
- 2019
- [j176]Erik D. Demaine, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, Somnath Sikdar, Blair D. Sullivan:
Structural sparsity of complex networks: Bounded expansion in random models and real-world graphs. J. Comput. Syst. Sci. 105: 199-241 (2019) - [j175]Katsuhisa Yamanaka, Erik D. Demaine, Takashi Horiyama, Akitoshi Kawamura, Shin-Ichi Nakano, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno:
Sequentially Swapping Colored Tokens on Graphs. J. Graph Algorithms Appl. 23(1): 3-27 (2019) - [j174]Aaron T. Becker, Erik D. Demaine, Sándor P. Fekete, Jarrett Lonsford, Rose Morris-Wright:
Particle computation: complexity, algorithms, and logic. Nat. Comput. 18(1): 181-201 (2019) - [j173]Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Henk Meijer, Christian Scheffer:
Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch. SIAM J. Comput. 48(6): 1727-1762 (2019) - [c297]Oswin Aichholzer, Hugo A. Akitaya, Kenneth C. Cheung, Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Linda Kleist, Irina Kostitsyna, Maarten Löffler, Zuzana Masárová, Klara Mundilova, Christiane Schmidt:
Folding Polyominoes with Holes into a Cube. CCCG 2019: 164-170 - [c296]Erik D. Demaine, John Iacono, Grigorios Koumoutsos, Stefan Langerman:
Belga B-Trees. CSR 2019: 93-105 - [c295]John Calvin Alumbaugh, Joshua J. Daymude, Erik D. Demaine, Matthew J. Patitz, Andréa W. Richa:
Simulation of Programmable Matter Systems Using Active Tile-Based Self-Assembly. DNA 2019: 140-158 - [c294]Hugo A. Akitaya, Esther M. Arkin, Mirela Damian, Erik D. Demaine, Vida Dujmovic, Robin Y. Flatland, Matias Korman, Belén Palop, Irene Parada, André van Renssen, Vera Sacristán:
Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers. ESA 2019: 3:1-3:14 - [c293]Erik D. Demaine, Timothy D. Goodrich, Kyle Kloster, Brian Lavallee, Quanquan C. Liu, Blair D. Sullivan, Ali Vakilian, Andrew van der Poel:
Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class. ESA 2019: 37:1-37:15 - [c292]Erik D. Demaine, David Eppstein, Adam Hesterberg, Kshitij Jain, Anna Lubiw, Ryuhei Uehara, Yushi Uno:
Reconfiguring Undirected Paths. WADS 2019: 353-365 - [i144]Hugo A. Akitaya, Cordelia Avery, Joseph Bergeron, Erik D. Demaine, Justin Kopinsky, Jason S. Ku:
Infinite All-Layers Simple Foldability. CoRR abs/1901.08564 (2019) - [i143]Erik D. Demaine, John Iacono, Grigorios Koumoutsos, Stefan Langerman:
Belga B-trees. CoRR abs/1903.03560 (2019) - [i142]Erik D. Demaine, David Eppstein, Adam Hesterberg, Kshitij Jain, Anna Lubiw, Ryuhei Uehara, Yushi Uno:
Reconfiguring Undirected Paths. CoRR abs/1905.00518 (2019) - [i141]John Calvin Alumbaugh, Joshua J. Daymude, Erik D. Demaine, Matthew J. Patitz, Andréa W. Richa:
Simulation of Programmable Matter Systems Using Active Tile-Based Self-Assembly. CoRR abs/1906.01773 (2019) - [i140]Pei-Chuan Chen, Erik D. Demaine, Chung-Shou Liao, Hao-Ting Wei:
Waiting is not easy but worth it: the online TSP on the line revisited. CoRR abs/1907.00317 (2019) - [i139]Erik D. Demaine, Martin L. Demaine, David Eppstein, Joseph O'Rourke:
Some Polycubes Have No Edge-Unzipping. CoRR abs/1907.08433 (2019) - [i138]Molly Baird, Sara C. Billey, Erik D. Demaine, Martin L. Demaine, David Eppstein, Sándor P. Fekete, Graham Gordon, Sean Griffin, Joseph S. B. Mitchell, Joshua P. Swanson:
Existence and hardness of conveyor belts. CoRR abs/1908.07668 (2019) - [i137]Hugo A. Akitaya, Esther M. Arkin, Mirela Damian, Erik D. Demaine, Vida Dujmovic, Robin Y. Flatland, Matias Korman, Belén Palop, Irene Parada, André van Renssen, Vera Sacristán:
Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers. CoRR abs/1908.07880 (2019) - [i136]Oswin Aichholzer, Hugo A. Akitaya, Kenneth C. Cheung, Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Linda Kleist, Irina Kostitsyna, Maarten Löffler, Zuzana Masárová, Klara Mundilova, Christiane Schmidt:
Folding Polyominoes with Holes into a Cube. CoRR abs/1910.09917 (2019) - 2018
- [j172]Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, Michiel H. M. Smid:
Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams. Algorithmica 80(11): 3316-3334 (2018) - [j171]Hugo A. Akitaya, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Ferran Hurtado, Jason S. Ku, Jayson Lynch:
Pachinko. Comput. Geom. 68: 226-242 (2018) - [j170]Zachary Abel, Erik D. Demaine, Martin L. Demaine, Hiro Ito, Jack Snoeyink, Ryuhei Uehara:
Bumpy pyramid folding. Comput. Geom. 75: 22-31 (2018) - [j169]Oswin Aichholzer, Michael Biro, Erik D. Demaine, Martin L. Demaine, David Eppstein, Sándor P. Fekete, Adam Hesterberg, Irina Kostitsyna, Christiane Schmidt:
Folding Polyominoes into (Poly)Cubes. Int. J. Comput. Geom. Appl. 28(3): 197-226 (2018) - [j168]Zachary Abel, Erik D. Demaine, Martin L. Demaine, David Eppstein, Anna Lubiw, Ryuhei Uehara:
Flat foldings of plane graphs with prescribed angles and edge lengths. J. Comput. Geom. 9(1): 74-93 (2018) - [j167]Zachary Abel, Victor Alvarez, Erik D. Demaine, Sándor P. Fekete, Aman Gour, Adam Hesterberg, Phillip Keldenich, Christian Scheffer:
Conflict-Free Coloring of Graphs. SIAM J. Discret. Math. 32(4): 2675-2702 (2018) - [j166]Erik D. Demaine, Mikhail Rudoy:
A simple proof that the (n2 - 1)-puzzle is hard. Theor. Comput. Sci. 732: 80-84 (2018) - [j165]Erik D. Demaine, Fabrizio Grandoni:
Editorial fun. Theor. Comput. Sci. 748: 1 (2018) - [j164]Erik D. Demaine, Fermi Ma, Ariel Schvartzman, Erik Waingarten, Scott Aaronson:
The fewest clues problem. Theor. Comput. Sci. 748: 28-39 (2018) - [j163]Byoungkwon An, Shuhei Miyashita, Aaron C. Ong, Michael Thomas Tolley, Martin L. Demaine, Erik D. Demaine, Robert J. Wood, Daniela Rus:
An End-to-End Approach to Self-Folding Origami Structures. IEEE Trans. Robotics 34(6): 1409-1424 (2018) - [c291]Jean Cardinal, Erik D. Demaine, David Eppstein, Robert A. Hearn, Andrew Winslow:
Reconfiguration of Satisfying Assignments and Subset Sums: Easy to Find, Hard to Connect. COCOON 2018: 365-377 - [c290]Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Christian Scheffer, Henk Meijer:
Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch. SoCG 2018: 29:1-29:15 - [c289]Erik D. Demaine, Jacob Hendricks, Meagan Olsen, Matthew J. Patitz, Trent A. Rogers, Nicolas Schabanel, Shinnosuke Seki, Hadley Thomas:
Know When to Fold 'Em: Self-assembly of Shapes by Folding in Oritatami. DNA 2018: 19-36 - [c288]Zachary Abel, Jeffrey Bosboom, Erik D. Demaine, Linus Hamilton, Adam Hesterberg, Justin Kopinsky, Jayson Lynch, Mikhail Rudoy:
Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible. FUN 2018: 3:1-3:21 - [c287]Jeffrey Bosboom, Erik D. Demaine, Mikhail Rudoy:
Computational Complexity of Generalized Push Fight. FUN 2018: 11:1-11:21 - [c286]Erik D. Demaine, Isaac Grosof, Jayson Lynch, Mikhail Rudoy:
Computational Complexity of Motion Planning of a Robot through Simple Gadgets. FUN 2018: 18:1-18:21 - [c285]Erik D. Demaine, Joshua Lockhart, Jayson Lynch:
The Computational Complexity of Portal and Other 3D Video Games. FUN 2018: 19:1-19:22 - [c284]Erik D. Demaine, Andrea Lincoln, Quanquan C. Liu, Jayson Lynch, Virginia Vassilevska Williams:
Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy. ITCS 2018: 34:1-34:23 - [c283]Zachary Abel, Hugo A. Akitaya, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Matias Korman, Jason S. Ku, Jayson Lynch:
Negative Instance for the Edge Patrolling Beacon Problem. JCDCGGG 2018: 28-35 - [c282]Hugo A. Akitaya, Brad Ballinger, Mirela Damian, Erik D. Demaine, Martin L. Demaine, Robin Y. Flatland, Irina Kostitsyna, Jason S. Ku, Stefan Langerman, Joseph O'Rourke, Ryuhei Uehara:
Toward Unfolding Doubly Covered n-Stars. JCDCGGG 2018: 122-135 - [c281]Erik D. Demaine, Martin L. Demaine, Ryuhei Uehara, Yushi Uno, Andrew Winslow:
Packing Cube Nets into Rectangles with O(1) Holes. JCDCGGG 2018: 152-164 - [c280]Erik D. Demaine, Quanquan C. Liu:
Red-Blue Pebble Game: Complexity of Computing the Trade-Off between Cache Size and Memory Transfers. SPAA 2018: 195-204 - [c279]Erik D. Demaine, Sarah Eisenstat, Mikhail Rudoy:
Solving the Rubik's Cube Optimally is NP-complete. STACS 2018: 24:1-24:13 - [c278]Erik D. Demaine, Mikhail Rudoy:
Tree-Residue Vertex-Breaking: a new tool for proving hardness. SWAT 2018: 32:1-32:14 - [c277]Lijie Chen, Erik D. Demaine, Yuzhou Gu, Virginia Vassilevska Williams, Yinzhan Xu, Yuancheng Yu:
Nearly Optimal Separation Between Partially and Fully Retroactive Data Structures. SWAT 2018: 33:1-33:12 - [i135]Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Henk Meijer, Christian Scheffer:
Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch. CoRR abs/1801.01689 (2018) - [i134]Jin Akiyama, Erik D. Demaine, Stefan Langerman:
Polyhedral Characterization of Reversible Hinged Dissections. CoRR abs/1803.01172 (2018) - [i133]Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Roderick Kimball, Justin Kopinsky:
Path Puzzles: Discrete Tomography with a Path Constraint is Hard. CoRR abs/1803.01176 (2018) - [i132]Jeffrey Bosboom, Erik D. Demaine, Mikhail Rudoy:
Computational Complexity of Generalized Push Fight. CoRR abs/1803.03708 (2018) - [i131]Lijie Chen, Erik D. Demaine, Yuzhou Gu, Virginia Vassilevska Williams, Yinzhan Xu, Yuancheng Yu:
Nearly Optimal Separation Between Partially And Fully Retroactive Data Structures. CoRR abs/1804.06932 (2018) - [i130]Zachary Abel, Jeffrey Bosboom, Erik D. Demaine, Linus Hamilton, Adam Hesterberg, Justin Kopinsky, Jayson Lynch, Mikhail Rudoy:
Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible. CoRR abs/1804.10193 (2018) - [i129]Jean Cardinal, Erik D. Demaine, David Eppstein, Robert A. Hearn, Andrew Winslow:
Reconfiguration of Satisfying Assignments and Subset Sums: Easy to Find, Hard to Connect. CoRR abs/1805.04055 (2018) - [i128]Erik D. Demaine, Timothy D. Goodrich, Kyle Kloster, Brian Lavallee, Quanquan C. Liu, Blair D. Sullivan, Ali Vakilian, Andrew van der Poel:
Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class. CoRR abs/1806.02771 (2018) - [i127]Erik D. Demaine, Isaac Grosof, Jayson Lynch, Mikhail Rudoy:
Computational Complexity of Motion Planning of a Robot through Simple Gadgets. CoRR abs/1806.03539 (2018) - [i126]Jeffrey Bosboom, Spencer Congero, Erik D. Demaine, Martin L. Demaine, Jayson Lynch:
Losing at Checkers is Hard. CoRR abs/1806.05657 (2018) - [i125]Erik D. Demaine, Jacob Hendricks, Meagan Olsen, Matthew J. Patitz, Trent A. Rogers, Nicolas Schabanel, Shinnosuke Seki, Hadley Thomas:
Know When to Fold 'Em: Self-Assembly of Shapes by Folding in Oritatami. CoRR abs/1807.04682 (2018) - [i124]Erik D. Demaine, Hiro Ito, Stefan Langerman, Jayson Lynch, Mikhail Rudoy, Kai Xiao:
Cookie Clicker. CoRR abs/1808.07540 (2018) - [i123]Hugo A. Akitaya, Erik D. Demaine, Takashi Horiyama, Thomas C. Hull, Jason S. Ku, Tomohiro Tachi:
Rigid Foldability is NP-Hard. CoRR abs/1812.01160 (2018) - [i122]Erik D. Demaine, Martin L. Demaine, David A. Huffman, Duks Koschitz, Tomohiro Tachi:
Conic Crease Patterns with Reflecting Rule Lines. CoRR abs/1812.01167 (2018) - [i121]Erik D. Demaine, Dylan H. Hendrickson, Jayson Lynch:
A General Theory of Motion Planning Complexity: Characterizing Which Gadgets Make Games Hard. CoRR abs/1812.03592 (2018) - 2017
- [j162]Erik D. Demaine, André Schulz:
Embedding Stacked Polytopes on a Polynomial-Size Grid. Discret. Comput. Geom. 57(4): 782-809 (2017) - [j161]Mirela Damian, Erik D. Demaine, Robin Y. Flatland, Joseph O'Rourke:
Unfolding Genus-2 Orthogonal Polyhedra with Linear Refinement. Graphs Comb. 33(5): 1357-1379 (2017) - [j160]Erik D. Demaine, Varun Ganesan, Vladislav Kontsevoi, Qipeng Liu, Quanquan C. Liu, Fermi Ma, Ofir Nachum, Aaron Sidford, Erik Waingarten, Daniel Ziegler:
Arboral satisfaction: Recognition and LP approximation. Inf. Process. Lett. 127: 1-5 (2017) - [j159]Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Adam Hesterberg, Andrea Lincoln, Jayson Lynch, Yun William Yu:
Total Tetris: Tetris with Monominoes, Dominoes, Trominoes, Pentominoes, ... J. Inf. Process. 25: 515-527 (2017) - [j158]Hugo A. Akitaya, Erik D. Demaine, Jason S. Ku:
Simple Folding is Really Hard. J. Inf. Process. 25: 580-589 (2017) - [j157]Yasuhiko Asao, Erik D. Demaine, Martin L. Demaine, Hideaki Hosaka, Akitoshi Kawamura, Tomohiro Tachi, Kazune Takahashi:
Folding and Punching Paper. J. Inf. Process. 25: 590-600 (2017) - [j156]Erik D. Demaine, Jason S. Ku:
Folded Structures Satisfying Multiple Conditions. J. Inf. Process. 25: 601-609 (2017) - [j155]Zachary Abel, Brad Ballinger, Erik D. Demaine, Martin L. Demaine, Jeff Erickson, Adam Hesterberg, Hiro Ito, Irina Kostitsyna, Jayson Lynch, Ryuhei Uehara:
Unfolding and Dissection of Multiple Cubes, Tetrahedra, and Doubly Covered Squares. J. Inf. Process. 25: 610-615 (2017) - [j154]Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Pasin Manurangsi, Anak Yodpinyanee:
Even 1 × n Edge-Matching and Jigsaw Puzzles are Really Hard. J. Inf. Process. 25: 682-694 (2017) - [j153]Erik D. Demaine, Sándor P. Fekete, Christian Scheffer, Arne Schmidt:
New geometric algorithms for fully connected staged self-assembly. Theor. Comput. Sci. 671: 4-18 (2017) - [c276]Erik D. Demaine, Matias Korman, André van Renssen, Marcel Roeloffzen:
Snipperclips: Cutting Tools into Desired Polygons using Themselves. CCCG 2017: 56-61 - [c275]Amartya Shankha Biswas, Erik D. Demaine:
Common Development of Prisms, Anti-Prisms, Tetrahedra, and Wedges. CCCG 2017: 202-207 - [c274]Byoungkwon An, Erik D. Demaine, Martin L. Demaine, Jason S. Ku:
Computing 3SAT on a Fold-and-Cut Machine. CCCG 2017: 208-213 - [c273]Erik D. Demaine, Isaac Grosof, Jayson Lynch:
Push-Pull Block Puzzles are Hard. CIAC 2017: 177-195 - [c272]Erik D. Demaine, Tomohiro Tachi:
Origamizer: A Practical Algorithm for Folding Any Polyhedron. SoCG 2017: 34:1-34:16 - [c271]Hugo A. Akitaya, Erik D. Demaine, Adam Hesterberg, Quanquan C. Liu:
Upward Partitioned Book Embeddings. GD 2017: 210-223 - [c270]Cameron T. Chalk, Erik D. Demaine, Martin L. Demaine, Eric Martinez, Robert T. Schweller, Luis Vega, Tim Wylie:
Universal Shape Replicators via Self-Assembly with Attractive and Repulsive Forces. SODA 2017: 225-238 - [c269]Zachary Abel, Victor Alvarez, Erik D. Demaine, Sándor P. Fekete, Aman Gour, Adam Hesterberg, Phillip Keldenich, Christian Scheffer:
Three Colors Suffice: Conflict-Free Coloring of Planar Graphs. SODA 2017: 1951-1963 - [c268]Nadia M. Benbernou, Erik D. Demaine, Martin L. Demaine, Anna Lubiw:
Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron. WADS 2017: 109-120 - [c267]Erik D. Demaine, Quanquan C. Liu:
Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs. WADS 2017: 313-324 - [c266]Katsuhisa Yamanaka, Erik D. Demaine, Takashi Horiyama, Akitoshi Kawamura, Shin-Ichi Nakano, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno:
Sequentially Swapping Colored Tokens on Graphs. WALCOM 2017: 435-447 - [i120]Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Pasin Manurangsi, Anak Yodpinyanee:
Even 1×n Edge-Matching and Jigsaw Puzzles are Really Hard. CoRR abs/1701.00146 (2017) - [i119]Zachary Abel, Victor Alvarez, Aman Gour, Adam Hesterberg, Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Christian Scheffer:
Three Colors Suffice: Conflict-Free Coloring of Planar Graphs. CoRR abs/1701.05999 (2017) - [i118]Erik D. Demaine, Matias Korman, Jason S. Ku, Joseph S. B. Mitchell, Yota Otachi, André van Renssen, Marcel Roeloffzen, Ryuhei Uehara, Yushi Uno:
Symmetric Assembly Puzzles are Hard, Beyond a Few Pieces. CoRR abs/1703.02671 (2017) - [i117]Mirela Damian, Erik D. Demaine, Muriel Dulieu, Robin Y. Flatland, Hella Hoffman, Thomas C. Hull, Jayson Lynch, Suneeta Ramaswami:
Minimal forcing sets for 1D origami. CoRR abs/1703.06373 (2017) - [i116]Erik D. Demaine, Sarah Eisenstat, Mikhail Rudoy:
Solving the Rubik's Cube Optimally is NP-complete. CoRR abs/1706.06708 (2017) - [i115]Erik D. Demaine, Mikhail Rudoy:
Tree-Residue Vertex-Breaking: a new tool for proving hardness. CoRR abs/1706.07900 (2017) - [i114]Erik D. Demaine, Mikhail Rudoy:
Hamiltonicity is Hard in Thin or Polygonal Grid Graphs, but Easy in Thin Polygonal Grid Graphs. CoRR abs/1706.10046 (2017) - [i113]Erik D. Demaine, Mikhail Rudoy:
A simple proof that the $(n^2-1)$-puzzle is hard. CoRR abs/1707.03146 (2017) - [i112]Erik D. Demaine, Quanquan C. Liu:
Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs. CoRR abs/1707.06343 (2017) - [i111]Hugo A. Akitaya, Erik D. Demaine, Adam Hesterberg, Quanquan C. Liu:
Upward Partitioned Book Embeddings. CoRR abs/1708.06730 (2017) - [i110]Erik D. Demaine, Isaac Grosof, Jayson Lynch:
Push-Pull Block Puzzles are Hard. CoRR abs/1709.01241 (2017) - [i109]Erik D. Demaine, Andrea Lincoln, Quanquan C. Liu, Jayson Lynch, Virginia Vassilevska Williams:
Fine-Grained I/O Complexity via Reductions: New lower bounds, faster algorithms, and a time hierarchy. CoRR abs/1711.07960 (2017) - [i108]Aaron T. Becker, Erik D. Demaine, Sándor P. Fekete, Jarrett Lonsford, Rose Morris-Wright:
Particle Computation: Complexity, Algorithms, and Logic. CoRR abs/1712.01197 (2017) - [i107]Oswin Aichholzer, Michael Biro, Erik D. Demaine, Martin L. Demaine, David Eppstein, Sándor P. Fekete, Adam Hesterberg, Irina Kostitsyna, Christiane Schmidt:
Folding Polyominoes into (Poly)Cubes. CoRR abs/1712.09317 (2017) - 2016
- [j152]Erik D. Demaine, Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller, Scott M. Summers, Damien Woods:
The Two-Handed Tile Assembly Model is not Intrinsically Universal. Algorithmica 74(2): 812-850 (2016) - [j151]Erik D. Demaine, David Eppstein, Adam Hesterberg, Hiro Ito, Anna Lubiw, Ryuhei Uehara, Yushi Uno:
Folding a paper strip to minimize thickness. J. Discrete Algorithms 36: 18-26 (2016) - [j150]Zachary Abel, Jason H. Cantarella, Erik D. Demaine, David Eppstein, Thomas C. Hull, Jason S. Ku, Robert J. Lang, Tomohiro Tachi:
Rigid origami vertices: conditions and forcing sets. J. Comput. Geom. 7(1): 171-184 (2016) - [c265]Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, Tao B. Schardl:
Who Needs Crossings? Hardness of Plane Graph Rigidity. SoCG 2016: 3:1-3:15 - [c264]Erik D. Demaine, Fermi Ma, Ariel Schvartzman, Erik Waingarten, Scott Aaronson:
The Fewest Clues Problem. FUN 2016: 12:1-12:12 - [c263]Erik D. Demaine, Giovanni Viglietta, Aaron Williams:
Super Mario Bros. is Harder/Easier Than We Thought. FUN 2016: 13:1-13:14 - [c262]Aviv Adler, Constantinos Daskalakis, Erik D. Demaine:
The Complexity of Hex and the Jordan Curve Theorem. ICALP 2016: 24:1-24:14 - [c261]Erik D. Demaine, Jayson Lynch, Geronimo J. Mirano, Nirvan Tyagi:
Energy-Efficient Algorithms. ITCS 2016: 321-332 - [c260]Nirvan Tyagi, Jayson Lynch, Erik D. Demaine:
Toward an Energy Efficient Language and Compiler for (Partially) Reversible Algorithms. RC 2016: 121-136 - [c259]Michael A. Bender, Erik D. Demaine, Roozbeh Ebrahimi, Jeremy T. Fineman, Rob Johnson, Andrea Lincoln, Jayson Lynch, Samuel McCauley:
Cache-Adaptive Analysis. SPAA 2016: 135-144 - [c258]MohammadHossein Bateni, Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx:
A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting. STOC 2016: 570-583 - [e5]Erik D. Demaine, Fabrizio Grandoni:
8th International Conference on Fun with Algorithms, FUN 2016, June 8-10, 2016, La Maddalena, Italy. LIPIcs 49, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2016, ISBN 978-3-95977-005-7 [contents] - [r6]Mohammad Taghi Hajiaghayi, Erik D. Demaine:
Approximation Schemes for Planar Graph Problems. Encyclopedia of Algorithms 2016: 133-137 - [r5]Fedor V. Fomin, Erik D. Demaine, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos:
Bidimensionality. Encyclopedia of Algorithms 2016: 203-207 - [r4]Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, Morteza Zadimoghaddam:
Network Creation Games. Encyclopedia of Algorithms 2016: 1408-1412 - [i106]Hugo A. Akitaya, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Ferran Hurtado, Jason S. Ku, Jayson Lynch:
Pachinko. CoRR abs/1601.05706 (2016) - [i105]Jason S. Ku, Erik D. Demaine:
Folding Flat Crease Patterns with Thick Materials. CoRR abs/1601.05747 (2016) - [i104]Erik D. Demaine, Jayson Lynch, Geronimo J. Mirano, Nirvan Tyagi:
Energy-Efficient Algorithms. CoRR abs/1605.08448 (2016) - [i103]Nirvan Tyagi, Jayson Lynch, Erik D. Demaine:
Toward an Energy Efficient Language and Compiler for (Partially) Reversible Algorithms. CoRR abs/1605.08475 (2016) - [i102]Kyle Burke, Erik D. Demaine, Harrison Gregg, Robert A. Hearn, Adam Hesterberg, Michael Hoffmann, Hiro Ito, Irina Kostitsyna, Jody Leonard, Maarten Löffler, Aaron Santiago, Christiane Schmidt, Ryuhei Uehara, Yushi Uno, Aaron Williams:
Single-Player and Two-Player Buttons & Scissors Games. CoRR abs/1607.01826 (2016) - [i101]William S. Moses, Erik D. Demaine:
Computational Complexity of Arranging Music. CoRR abs/1607.04220 (2016) - [i100]Cameron T. Chalk, Erik D. Demaine, Martin L. Demaine, Eric Martinez, Robert T. Schweller, Luis Vega, Tim Wylie:
Universal Shape Replicators via Self-Assembly with Attractive and Repulsive Forces. CoRR abs/1608.00477 (2016) - [i99]Mirela Damian, Erik D. Demaine, Robin Y. Flatland, Joseph O'Rourke:
Unfolding Genus-2 Orthogonal Polyhedra with Linear Refinement. CoRR abs/1611.00106 (2016) - [i98]Nadia M. Benbernou, Erik D. Demaine, Martin L. Demaine, Anna Lubiw:
Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron. CoRR abs/1611.03187 (2016) - [i97]Erik D. Demaine, Joshua Lockhart, Jayson Lynch:
The Computational Complexity of Portal and Other 3D Video Games. CoRR abs/1611.10319 (2016) - 2015
- [j149]Erik D. Demaine, John Iacono, Stefan Langerman:
Worst-Case Optimal Tree Layout in External Memory. Algorithmica 72(2): 369-378 (2015) - [j148]Aaron B. Adcock, Erik D. Demaine, Martin L. Demaine, Michael P. O'Brien, Felix Reidl, Fernando Sánchez Villaamil, Blair D. Sullivan:
Zig-Zag Numberlink is NP-Complete. J. Inf. Process. 23(3): 239-245 (2015) - [j147]Erik D. Demaine, Fermi Ma, Matthew Susskind, Erik Waingarten:
You Should Be Scared of German Ghost. J. Inf. Process. 23(3): 293-298 (2015) - [j146]Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, Takeaki Uno:
Swapping labeled tokens on graphs. Theor. Comput. Sci. 586: 81-94 (2015) - [j145]Erik D. Demaine, Martin L. Demaine:
Fun with fonts: Algorithmic typography. Theor. Comput. Sci. 586: 111-119 (2015) - [j144]Greg Aloupis, Erik D. Demaine, Alan Guo, Giovanni Viglietta:
Classic Nintendo games are (computationally) hard. Theor. Comput. Sci. 586: 135-160 (2015) - [j143]Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, Takeshi Yamada:
Linear-time algorithm for sliding tokens on trees. Theor. Comput. Sci. 600: 132-142 (2015) - [c257]Aviv Adler, Michael Biro, Erik D. Demaine, Mikhail Rudoy, Christiane Schmidt:
Computational complexity of numberless Shakashaka. CCCG 2015 - [c256]Oswin Aichholzer, Michael Biro, Erik D. Demaine, Martin L. Demaine, David Eppstein, Sándor P. Fekete, Adam Hesterberg, Irina Kostitsyna, Christiane Schmidt:
Folding Polyominoes into (Poly)Cubes. CCCG 2015 - [c255]Aaron T. Becker, Erik D. Demaine, Sándor P. Fekete, Hamed Mohtasham Shad, Rose Morris-Wright:
Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals. SoCG 2015: 16-18 - [c254]Erik D. Demaine, Sándor P. Fekete, Christian Scheffer, Arne Schmidt:
New Geometric Algorithms for Fully Connected Staged Self-Assembly. DNA 2015: 104-116 - [c253]Seung Man Oh, Godfried T. Toussaint, Erik D. Demaine, Martin L. Demaine:
A Dissimilarity Measure for Comparing Origami Crease Patterns. ICPRAM (1) 2015: 386-393 - [c252]Hamed Mohtasham Shad, Rose Morris-Wright, Erik D. Demaine, Sándor P. Fekete, Aaron T. Becker:
Particle computation: Device fan-out and binary memory. ICRA 2015: 5384-5389 - [c251]Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Jayson Lynch, Pasin Manurangsi, Mikhail Rudoy, Anak Yodpinyanee:
Dissection with the Fewest Pieces is Hard, Even to Approximate. JCDCGG 2015: 37-48 - [c250]Jeffrey Bosboom, Erik D. Demaine, Adam Hesterberg, Jayson Lynch, Erik Waingarten:
Mario Kart Is Hard. JCDCGG 2015: 49-59 - [c249]Kyle Burke, Erik D. Demaine, Harrison Gregg, Robert A. Hearn, Adam Hesterberg, Michael Hoffmann, Hiro Ito, Irina Kostitsyna, Jody Leonard, Maarten Löffler, Aaron Santiago, Christiane Schmidt, Ryuhei Uehara, Yushi Uno, Aaron Williams:
Single-Player and Two-Player Buttons & Scissors Games - (Extended Abstract). JCDCGG 2015: 60-72 - [c248]Erik D. Demaine, Martin L. Demaine, Jin-ichi Itoh, Chie Nara:
Continuous Flattening of Orthogonal Polyhedra. JCDCGG 2015: 85-93 - [c247]Erik D. Demaine, Stefan Langerman:
Bust-a-Move/Puzzle Bobble Is NP-complete. JCDCGG 2015: 94-104 - [c246]Hugo A. Akitaya, Kenneth C. Cheung, Erik D. Demaine, Takashi Horiyama, Thomas C. Hull, Jason S. Ku, Tomohiro Tachi, Ryuhei Uehara:
Box Pleating is Hard. JCDCGG 2015: 167-179 - [c245]Erik D. Demaine, Matias Korman, Jason S. Ku, Joseph S. B. Mitchell, Yota Otachi, André van Renssen, Marcel Roeloffzen, Ryuhei Uehara, Yushi Uno:
Symmetric Assembly Puzzles are Hard, Beyond a Few Pieces. JCDCGG 2015: 180-192 - [c244]Erik D. Demaine, Vineet Gopal, William Hasenplaugh:
Cache-Oblivious Iterated Predecessor Queries via Range Coalescing. WADS 2015: 249-262 - [c243]Erik D. Demaine, Tim Kaler, Quanquan C. Liu, Aaron Sidford, Adam Yedidia:
Polylogarithmic Fully Retroactive Priority Queues via Hierarchical Checkpointing. WADS 2015: 263-275 - [c242]Erik D. Demaine, David Eppstein, Adam Hesterberg, Hiro Ito, Anna Lubiw, Ryuhei Uehara, Yushi Uno:
Folding a Paper Strip to Minimize Thickness. WALCOM 2015: 113-124 - [i96]Erik D. Demaine, Martin L. Demaine, David A. Huffman, Duks Koschitz, Tomohiro Tachi:
Characterization of Curved Creases and Rulings: Design and Analysis of Lens Tessellations. CoRR abs/1502.03191 (2015) - [i95]Erik D. Demaine, Sándor P. Fekete, Christian Scheffer, Arne Schmidt:
New Geometric Algorithms for Fully Connected Staged Self-Assembly. CoRR abs/1505.07862 (2015) - [i94]Erik D. Demaine, Stefan Langerman:
Bust-a-Move/Puzzle Bobble is NP-Complete. CoRR abs/1506.08409 (2015) - [i93]Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Jayson Lynch, Pasin Manurangsi, Mikhail Rudoy, Anak Yodpinyanee:
Dissection with the Fewest Pieces is Hard, Even to Approximate. CoRR abs/1512.06706 (2015) - 2014
- [j142]Glencora Borradaile, Erik D. Demaine, Siamak Tazari:
Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs. Algorithmica 68(2): 287-311 (2014) - [j141]Erik D. Demaine, Gad M. Landau, Oren Weimann:
On Cartesian Trees and Range Minimum Queries. Algorithmica 68(3): 610-625 (2014) - [j140]David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Patrascu, Perouz Taslakian:
Necklaces, Convolutions, and X+Y. Algorithmica 69(2): 294-314 (2014) - [j139]Erik D. Demaine, Martin L. Demaine, Jin-ichi Itoh, Anna Lubiw, Chie Nara, Joseph O'Rourke:
Reprint of: Refold rigidity of convex polyhedra. Comput. Geom. 47(3): 507-517 (2014) - [j138]Mirela Damian, Erik D. Demaine, Robin Y. Flatland:
Unfolding Orthogonal Polyhedra with Quadratic Refinement: The Delta-Unfolding Algorithm. Graphs Comb. 30(1): 125-140 (2014) - [j137]Zachary Abel, Erik D. Demaine, Martin L. Demaine, Takashi Horiyama, Ryuhei Uehara:
Computational Complexity of Piano-Hinged Dissections. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 97-A(6): 1206-1212 (2014) - [j136]Erik D. Demaine, Yoshio Okamoto, Ryuhei Uehara, Yushi Uno:
Computational Complexity and an Integer Programming Model of Shakashaka. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 97-A(6): 1213-1219 (2014) - [j135]Takehiro Ito, Erik D. Demaine:
Approximability of the subset sum reconfiguration problem. J. Comb. Optim. 28(3): 639-654 (2014) - [j134]Oswin Aichholzer, Greg Aloupis, Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Michael Hoffmann, Anna Lubiw, Jack Snoeyink, Andrew Winslow:
Covering Folded Shapes. J. Comput. Geom. 5(1): 150-167 (2014) - [j133]Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph S. B. Mitchell, Ronald L. Rivest, Mihai Patrascu:
Picture-Hanging Puzzles. Theory Comput. Syst. 54(4): 531-550 (2014) - [j132]Noga Alon, Erik D. Demaine, MohammadTaghi Hajiaghayi, Panagiotis Kanellopoulos, Tom Leighton:
Correction: Basic Network Creation Games. SIAM J. Discret. Math. 28(3): 1638-1640 (2014) - [j131]Erik D. Demaine, Mohammad Taghi Hajiaghayi, Philip N. Klein:
Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs. ACM Trans. Algorithms 10(3): 13:1-13:20 (2014) - [j130]Erik D. Demaine, Mohammad Taghi Hajiaghayi, Dániel Marx:
Minimizing Movement: Fixed-Parameter Tractability. ACM Trans. Algorithms 11(2): 14:1-14:29 (2014) - [j129]Erik D. Demaine, Martin L. Demaine, Nicholas J. A. Harvey, Ryuhei Uehara, Takeaki Uno, Yushi Uno:
UNO is hard, even for a single player. Theor. Comput. Sci. 521: 51-61 (2014) - [c241]Zachary Abel, Erik D. Demaine, Martin L. Demaine, Hiro Ito, Jack Snoeyink, Ryuhei Uehara:
Bumpy Pyramid Folding. CCCG 2014 - [c240]Zachary Abel, Erik D. Demaine, Martin L. Demaine, Jin-ichi Itoh, Anna Lubiw, Chie Nara, Joseph O'Rourke:
Continuously Flattening Polyhedra Using Straight Skeletons. SoCG 2014: 396 - [c239]Erik D. Demaine, Martin L. Demaine:
Fun with Fonts: Algorithmic Typography. FUN 2014: 16-27 - [c238]Greg Aloupis, Erik D. Demaine, Alan Guo, Giovanni Viglietta:
Classic Nintendo Games Are (Computationally) Hard. FUN 2014: 40-51 - [c237]Erik D. Demaine, Fermi Ma, Erik Waingarten:
Playing Dominoes Is Hard, Except by Yourself. FUN 2014: 137-146 - [c236]Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, Takeaki Uno:
Swapping Labeled Tokens on Graphs. FUN 2014: 364-375 - [c235]Zachary Abel, Erik D. Demaine, Martin L. Demaine, David Eppstein, Anna Lubiw, Ryuhei Uehara:
Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths. GD 2014: 272-283 - [c234]Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, Robert T. Schweller, Andrew Winslow, Damien Woods:
One Tile to Rule Them All: Simulating Any Tile Assembly System with a Single Universal Tile. ICALP (1) 2014: 368-379 - [c233]Erik D. Demaine, Yamming Huang, Chung-Shou Liao, Kunihiko Sadakane:
Canadians Should Travel Randomly. ICALP (1) 2014: 380-391 - [c232]Byoungkwon An, Shuhei Miyashita, Michael Thomas Tolley, Daniel M. Aukes, Laura Meeker, Erik D. Demaine, Martin L. Demaine, Robert J. Wood, Daniela Rus:
An end-to-end approach to making self-folded 3D surface shapes by uniform heating. ICRA 2014: 1466-1473 - [c231]Aaron T. Becker, Erik D. Demaine, Sándor P. Fekete, James McLurkin:
Particle computation: Designing worlds to control robot swarms with only global signals. ICRA 2014: 6751-6756 - [c230]Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, Takeshi Yamada:
Polynomial-Time Algorithm for Sliding Tokens on Trees. ISAAC 2014: 389-400 - [c229]Erik D. Demaine, Piotr Indyk, Sepideh Mahabadi, Ali Vakilian:
On Streaming and Communication Complexity of the Set Cover Problem. DISC 2014: 484-498 - [c228]Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, David L. Malec, S. Raghavan, Anshul Sawant, Morteza Zadimoghaddam:
How to influence people with partial incentives. WWW 2014: 937-948 - [i92]Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, David L. Malec, S. Raghavan, Anshul Sawant, Morteza Zadimoghaddam:
How to Influence People with Partial Incentives. CoRR abs/1401.7970 (2014) - [i91]Aaron T. Becker, Erik D. Demaine, Sándor P. Fekete, James McLurkin:
Particle Computation: Designing Worlds to Control Robot Swarms with only Global Signals. CoRR abs/1402.3749 (2014) - [i90]Erik D. Demaine, André Schulz:
Embedding Stacked Polytopes on a Polynomial-Size Grid. CoRR abs/1403.7980 (2014) - [i89]Erik D. Demaine, Martin L. Demaine:
Fun with Fonts: Algorithmic Typography. CoRR abs/1404.1775 (2014) - [i88]Oswin Aichholzer, Greg Aloupis, Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Michael Hoffmann, Anna Lubiw, Jack Snoeyink, Andrew Winslow:
Covering Folded Shapes. CoRR abs/1405.2378 (2014) - [i87]Erik D. Demaine, Nathan Pinsker, Jon Schneider:
Fast Dynamic Pointer Following via Link-Cut Trees. CoRR abs/1405.3739 (2014) - [i86]Erik D. Demaine, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, Somnath Sikdar, Blair D. Sullivan:
Structural Sparsity of Complex Networks: Random Graph Models and Linear Algorithms. CoRR abs/1406.2587 (2014) - [i85]Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, Takeshi Yamada:
Polynomial-Time Algorithm for Sliding Tokens on Trees. CoRR abs/1406.6576 (2014) - [i84]Zachary Abel, Erik D. Demaine, Martin L. Demaine, David Eppstein, Anna Lubiw, Ryuhei Uehara:
Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths. CoRR abs/1408.6771 (2014) - [i83]Aaron B. Adcock, Erik D. Demaine, Martin L. Demaine, Michael P. O'Brien, Felix Reidl, Fernando Sánchez Villaamil, Blair D. Sullivan:
Zig-Zag Numberlink is NP-Complete. CoRR abs/1410.5845 (2014) - [i82]Erik D. Demaine, Jason S. Ku:
Filling a Hole in a Crease Pattern: Isometric Mapping from Prescribed Boundary Folding. CoRR abs/1410.6520 (2014) - [i81]Erik D. Demaine, David Eppstein, Adam Hesterberg, Hiro Ito, Anna Lubiw, Ryuhei Uehara, Yushi Uno:
Folding a Paper Strip to Minimize Thickness. CoRR abs/1411.6371 (2014) - 2013
- [j128]Greg Aloupis, Jean Cardinal, Sébastien Collette, Erik D. Demaine, Martin L. Demaine, Muriel Dulieu, Ruy Fabila Monroy, Vi Hart, Ferran Hurtado, Stefan Langerman, Maria Saumell, Carlos Seara, Perouz Taslakian:
Non-crossing matchings of points with geometric objects. Comput. Geom. 46(1): 78-92 (2013) - [j127]Gill Barequet, Nadia M. Benbernou, David Charlton, Erik D. Demaine, Martin L. Demaine, Mashhood Ishaque, Anna Lubiw, André Schulz, Diane L. Souvaine, Godfried T. Toussaint, Andrew Winslow:
Bounded-degree polyhedronization of point sets. Comput. Geom. 46(2): 148-153 (2013) - [j126]Greg Aloupis, Nadia M. Benbernou, Mirela Damian, Erik D. Demaine, Robin Y. Flatland, John Iacono, Stefanie Wuhrer:
Efficient reconfiguration of lattice-based modular robots. Comput. Geom. 46(8): 917-928 (2013) - [j125]Erik D. Demaine, Martin L. Demaine, Jin-ichi Itoh, Anna Lubiw, Chie Nara, Joseph O'Rourke:
Refold rigidity of convex polyhedra. Comput. Geom. 46(8): 979-989 (2013) - [j124]Erik D. Demaine:
A Few Lessons I've Learned. Bull. EATCS 111 (2013) - [j123]Steve Butler, Erik D. Demaine, Ronald L. Graham, Tomohiro Tachi:
Constructing Points through Folding and Intersection. Int. J. Comput. Geom. Appl. 23(1): 49-64 (2013) - [j122]Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, Tao B. Schardl, Isaac Shapiro-Ellowitz:
Folding Equilateral Plane graphs. Int. J. Comput. Geom. Appl. 23(2): 75-92 (2013) - [j121]Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, Tao B. Schardl:
Finding a Hamiltonian Path in a Cube with Specified Turns is Hard. Inf. Media Technol. 8(3): 685-694 (2013) - [j120]Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Ilan Newman, Oren Weimann:
The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs. J. Comb. Optim. 25(1): 19-46 (2013) - [j119]Brad Ballinger, Nadia M. Benbernou, Prosenjit Bose, Mirela Damian, Erik D. Demaine, Vida Dujmovic, Robin Y. Flatland, Ferran Hurtado, John Iacono, Anna Lubiw, Pat Morin, Vera Sacristán Adinolfi, Diane L. Souvaine, Ryuhei Uehara:
Coverage with k-transmitters in the presence of obstacles. J. Comb. Optim. 25(2): 208-233 (2013) - [j118]Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, Tao B. Schardl:
Finding a Hamiltonian Path in a Cube with Specified Turns is Hard. J. Inf. Process. 21(3): 368-377 (2013) - [j117]Erik D. Demaine, Sarah Eisenstat, Mashhood Ishaque, Andrew Winslow:
One-dimensional staged self-assembly. Nat. Comput. 12(2): 247-258 (2013) - [j116]Erik D. Demaine, Mohammad Ghodsi, MohammadTaghi Hajiaghayi, Amin S. Sayedi-Roshkhar, Morteza Zadimoghaddam:
Scheduling to minimize gaps and power consumption. J. Sched. 16(2): 151-160 (2013) - [j115]Noga Alon, Erik D. Demaine, Mohammad Taghi Hajiaghayi, Tom Leighton:
Basic Network Creation Games. SIAM J. Discret. Math. 27(2): 656-668 (2013) - [c227]Aaron T. Becker, Erik D. Demaine, Sándor P. Fekete, Golnaz Habibi, James McLurkin:
Reconfiguring Massive Particle Swarms with Limited, Global Control. ALGOSENSORS 2013: 51-66 - [c226]Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Thomas D. Morgan, Ryuhei Uehara:
Variations on Instant Insanity. Space-Efficient Data Structures, Streams, and Algorithms 2013: 33-47 - [c225]Oswin Aichholzer, Greg Aloupis, Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Michael Hoffmann, Anna Lubiw, Jack Snoeyink, Andrew Winslow:
Covering Folded Shapes. CCCG 2013 - [c224]Erik D. Demaine, Martin L. Demaine, Ryuhei Uehara:
Zipper Unfoldability of Domes and Prismoids. CCCG 2013 - [c223]Erik D. Demaine, Yoshio Okamoto, Ryuhei Uehara, Yushi Uno:
Computational complexity and an integer programming model of Shakashaka. CCCG 2013 - [c222]Erik D. Demaine, John Iacono, Stefan Langerman, Özgür Özkan:
Combining Binary Search Trees. ICALP (1) 2013: 388-399 - [c221]Erik D. Demaine, Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller, Scott M. Summers, Damien Woods:
The Two-Handed Tile Assembly Model Is Not Intrinsically Universal. ICALP (1) 2013: 400-412 - [c220]Alex Cole, Erik D. Demaine, Eli Fox-Epstein:
On Wrapping Spheres and Cubes with Rectangular Paper. JCDCGG 2013: 31-43 - [c219]Erik D. Demaine, Morteza Zadimoghaddam:
Learning Disjunctions: Near-Optimal Trade-off between Mistakes and "I Don't Know's". SODA 2013: 1369-1379 - [c218]Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, Andrew Winslow:
Two Hands Are Better Than One (up to constant factors): Self-Assembly In The 2HAM vs. aTAM. STACS 2013: 172-184 - [c217]Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, André Schulz, Diane L. Souvaine, Giovanni Viglietta, Andrew Winslow:
Algorithms for Designing Pop-Up Cards. STACS 2013: 269-280 - [c216]Erik D. Demaine, Pavel Panchekha, David A. Wilson, Edward Z. Yang:
Blame Trees. WADS 2013: 280-290 - [i80]Erik D. Demaine, John Iacono, Stefan Langerman, Özgür Özkan:
Combining Binary Search Trees. CoRR abs/1304.7604 (2013) - [i79]Erik D. Demaine, Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller, Scott M. Summers, Damien Woods:
The two-handed tile assembly model is not intrinsically universal. CoRR abs/1306.6710 (2013) - [i78]Mirela Damian, Erik D. Demaine, Robin Y. Flatland:
Unfolding Orthogrids with Constant Refinement. CoRR abs/1310.4561 (2013) - [i77]Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, Dimitrios M. Thilikos:
Bidimensional Structures: Algorithms, Combinatorics and Logic (Dagstuhl Seminar 13121). Dagstuhl Reports 3(3): 51-74 (2013) - 2012
- [j114]Erik D. Demaine, Martin L. Demaine, Ryuhei Uehara:
Any Monotone Function Is Realized by Interlocked Polygons. Algorithms 5(1): 148-157 (2012) - [j113]Oswin Aichholzer, Franz Aurenhammer, Erik D. Demaine, Ferran Hurtado, Pedro Ramos, Jorge Urrutia:
On k-convex polygons. Comput. Geom. 45(3): 73-87 (2012) - [j112]Takehiro Ito, Marcin Kaminski, Erik D. Demaine:
Reconfiguration of list edge-colorings in a graph. Discret. Appl. Math. 160(15): 2199-2207 (2012) - [j111]Timothy G. Abbott, Zachary Abel, David Charlton, Erik D. Demaine, Martin L. Demaine, Scott Duke Kominers:
Hinged Dissections Exist. Discret. Comput. Geom. 47(1): 150-186 (2012) - [j110]David Charlton, Erik D. Demaine, Martin L. Demaine, Vida Dujmovic, Pat Morin, Ryuhei Uehara:
Ghost chimneys. Int. J. Comput. Geom. Appl. 22(3): 207-214 (2012) - [j109]Erik D. Demaine, Morteza Zadimoghaddam:
Constant Price of Anarchy in Network-Creation Games via Public-Service Advertising. Internet Math. 8(1-2): 29-45 (2012) - [j108]Tetsuo Asano, Erik D. Demaine, Martin L. Demaine, Ryuhei Uehara:
NP-completeness of generalized Kaboozle. Inf. Media Technol. 7(3): 1019-1024 (2012) - [j107]Tetsuo Asano, Erik D. Demaine, Martin L. Demaine, Ryuhei Uehara:
NP-completeness of generalized Kaboozle. J. Inf. Process. 20(3): 713-718 (2012) - [j106]Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, Morteza Zadimoghaddam:
The price of anarchy in network creation games. ACM Trans. Algorithms 8(2): 13:1-13:13 (2012) - [c215]Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph S. B. Mitchell, Ronald L. Rivest, Mihai Patrascu:
Picture-Hanging Puzzles. FUN 2012: 81-93 - [c214]Erik D. Demaine:
Origami Robots and Star Trek Replicators. ISAAC 2012: 3 - [i76]Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, Andrew Winslow:
Two Hands Are Better Than One (up to constant factors). CoRR abs/1201.1650 (2012) - [i75]Greg Aloupis, Erik D. Demaine, Alan Guo:
Classic Nintendo Games are (NP-)Hard. CoRR abs/1203.1895 (2012) - [i74]Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph S. B. Mitchell, Ronald L. Rivest, Mihai Patrascu:
Picture-Hanging Puzzles. CoRR abs/1203.3602 (2012) - [i73]Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx:
Minimizing Movement: Fixed-Parameter Tractability. CoRR abs/1205.6960 (2012) - [i72]Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, Robert T. Schweller, Andrew Winslow, Damien Woods:
One Tile to Rule Them All: Simulating Any Turing Machine, Tile Assembly System, or Tiling System with a Single Puzzle Piece. CoRR abs/1212.4756 (2012) - [i71]David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Patrascu, Perouz Taslakian:
Necklaces, Convolutions, and X+Y. CoRR abs/1212.4771 (2012) - 2011
- [j105]Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, Oren Weimann:
The Stackelberg Minimum Spanning Tree Game. Algorithmica 59(2): 129-144 (2011) - [j104]Erik D. Demaine, Sándor P. Fekete, Günter Rote, Nils Schweer, Daria Schymura, Mariano Zelke:
Integer point sets minimizing average pairwise L1 distance: What is the optimal shape of a town? Comput. Geom. 44(2): 82-94 (2011) - [j103]Hee-Kap Ahn, Sang Won Bae, Erik D. Demaine, Martin L. Demaine, Sang-Sub Kim, Matias Korman, Iris Reinbacher, Wanbin Son:
Covering points by disjoint boxes with outliers. Comput. Geom. 44(3): 178-190 (2011) - [j102]Jean Cardinal, Erik D. Demaine, Martin L. Demaine, Shinji Imahori, Tsuyoshi Ito, Masashi Kiyomi, Stefan Langerman, Ryuhei Uehara, Takeaki Uno:
Algorithmic Folding Complexity. Graphs Comb. 27(3): 341-351 (2011) - [j101]Erik D. Demaine, Martin L. Demaine, Vi Hart, John Iacono, Stefan Langerman, Joseph O'Rourke:
Continuous Blooming of Convex Polyhedra. Graphs Comb. 27(3): 363-376 (2011) - [j100]Erik D. Demaine, Martin L. Demaine, Vi Hart, Gregory N. Price, Tomohiro Tachi:
(Non)Existence of Pleated Folds: How Paper Folds Between Creases. Graphs Comb. 27(3): 377-397 (2011) - [j99]Greg Aloupis, Prosenjit Bose, Erik D. Demaine, Stefan Langerman, Henk Meijer, Mark H. Overmars, Godfried T. Toussaint:
Computing Signed Permutations of Polygons. Int. J. Comput. Geom. Appl. 21(1): 87-100 (2011) - [j98]Sachio Teramoto, Erik D. Demaine, Ryuhei Uehara:
The Voronoi game on graphs and its complexity. J. Graph Algorithms Appl. 15(4): 485-501 (2011) - [j97]Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Robin Y. Flatland, Stefan Langerman, Joseph O'Rourke, Val Pinciu, Suneeta Ramaswami, Vera Sacristán, Stefanie Wuhrer:
Efficient constant-velocity reconfiguration of crystalline robots. Robotica 29(1): 59-71 (2011) - [j96]Byoungkwon An, Nadia M. Benbernou, Erik D. Demaine, Daniela Rus:
Planning to fold multiple objects from a single self-folding sheet. Robotica 29(1): 87-102 (2011) - [j95]Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, Yushi Uno:
On the complexity of reconfiguration problems. Theor. Comput. Sci. 412(12-14): 1054-1065 (2011) - [j94]Kenneth C. Cheung, Erik D. Demaine, Jonathan Bachrach, Saul Griffith:
Programmable Assembly With Universally Foldable Strings (Moteins). IEEE Trans. Robotics 27(4): 718-729 (2011) - [c213]Piotr Berman, Erik D. Demaine, Morteza Zadimoghaddam:
O(1)-Approximations for Maximum Movement Problems. APPROX-RANDOM 2011: 62-74 - [c212]Zachary Abel, Erik D. Demaine:
Edge-Unfolding Orthogonal Polyhedra is Strongly NP-Complete. CCCG 2011 - [c211]Zachary Abel, Erik D. Demaine, Martin L. Demaine:
A Topologically Convex Vertex-Ununfoldable Polyhedron. CCCG 2011 - [c210]Zachary Abel, Erik D. Demaine, Martin L. Demaine, Hiroaki Matsui, Günter Rote, Ryuhei Uehara:
Common Developments of Several Different Orthogonal Boxes. CCCG 2011 - [c209]Oswin Aichholzer, Greg Aloupis, Erik D. Demaine, Martin L. Demaine, Vida Dujmovic, Ferran Hurtado, Anna Lubiw, Günter Rote, André Schulz, Diane L. Souvaine, Andrew Winslow:
Convexifying Polygons Without Losing Visibilities. CCCG 2011 - [c208]Sarah Eisenstat, Erik D. Demaine:
Expansive Motions for d-Dimensional Open Chains. CCCG 2011 - [c207]Giovanni Viglietta, Nadia M. Benbernou, Erik D. Demaine, Martin L. Demaine, Anastasia Kurdia, Joseph O'Rourke, Godfried T. Toussaint, Jorge Urrutia:
Edge-guarding Orthogonal Polyhedra. CCCG 2011 - [c206]Erik D. Demaine, Sarah Eisenstat, Jeffrey O. Shallit, David A. Wilson:
Remarks on Separating Words. DCFS 2011: 147-157 - [c205]Erik D. Demaine, Sarah Eisenstat, Mashhood Ishaque, Andrew Winslow:
One-Dimensional Staged Self-assembly. DNA 2011: 100-114 - [c204]Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, Andrew Winslow:
Algorithms for Solving Rubik's Cubes. ESA 2011: 689-700 - [c203]Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, Tao B. Schardl, Isaac Shapiro-Ellowitz:
Folding Equilateral Plane Graphs. ISAAC 2011: 574-583 - [c202]Erik D. Demaine, Anna Lubiw:
A Generalization of the Source Unfolding of Convex Polyhedra. EGC 2011: 185-199 - [c201]Greg Aloupis, Erik D. Demaine, Martin L. Demaine, Vida Dujmovic, John Iacono:
Meshes Preserving Minimum Feature Size. EGC 2011: 258-273 - [c200]Erik D. Demaine, André Schulz:
Embedding Stacked Polytopes on a Polynomial-Size Grid. SODA 2011: 1177-1187 - [c199]Erik D. Demaine:
Constructing Strings at the Nano Scale via Staged Self-assembly. SPIRE 2011: 1 - [c198]Erik D. Demaine, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers:
Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor (extended abstract). STACS 2011: 201-212 - [c197]Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi:
Contraction decomposition in h-minor-free graphs and algorithmic applications. STOC 2011: 441-450 - [c196]Takehiro Ito, Erik D. Demaine:
Approximability of the Subset Sum Reconfiguration Problem. TAMC 2011: 58-69 - [c195]Paul F. Christiano, Erik D. Demaine, Shaunak Kishore:
Lossless Fault-Tolerant Data Structures with Additive Overhead. WADS 2011: 243-254 - [c194]Erik D. Demaine, Sarah Eisenstat:
Flattening Fixed-Angle Chains Is Strongly NP-Hard. WADS 2011: 314-325 - [i70]Erik D. Demaine, Sarah Eisenstat, Jeffrey O. Shallit, David A. Wilson:
Remarks on separating words. CoRR abs/1103.4513 (2011) - [i69]Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, Andrew Winslow:
Algorithms for Solving Rubik's Cubes. CoRR abs/1106.5736 (2011) - [i68]Mirela Damian, Erik D. Demaine, Robin Y. Flatland:
Unfolding Orthogonal Polyhedra with Quadratic Refinement: The Delta-Unfolding Algorithm. CoRR abs/1112.4791 (2011) - 2010
- [j93]Erik D. Demaine, Stefan Langerman, Eric Price:
Confluently Persistent Tries for Efficient Version Control. Algorithmica 57(3): 462-483 (2010) - [j92]Erik D. Demaine, MohammadTaghi Hajiaghayi, Bojan Mohar:
Approximation algorithms via contraction decomposition. Comb. 30(5): 533-552 (2010) - [j91]Erik D. Demaine, Gregory N. Price:
Generalized D-Forms Have No Spurious Creases. Discret. Comput. Geom. 43(1): 179-186 (2010) - [j90]Robert Connelly, Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Stefan Langerman, Joseph S. B. Mitchell, Ares Ribó, Günter Rote:
Locked and Unlocked Chains of Planar Shapes. Discret. Comput. Geom. 44(2): 439-462 (2010) - [j89]Erik D. Demaine, John Iacono, Stefan Langerman:
Grid Vertex-Unfolding Orthostacks. Int. J. Comput. Geom. Appl. 20(3): 245-254 (2010) - [j88]Alan Brunton, Stefanie Wuhrer, Chang Shu, Prosenjit Bose, Erik D. Demaine:
Filling Holes in Triangular Meshes Using Digital Images by Curve Unfolding. Int. J. Shape Model. 16(1-2): 151-171 (2010) - [j87]Jonathan Bredin, Erik D. Demaine, Mohammad Taghi Hajiaghayi, Daniela Rus:
Deploying sensor networks with guaranteed fault tolerance. IEEE/ACM Trans. Netw. 18(1): 216-228 (2010) - [c193]David Charlton, Erik D. Demaine, Martin L. Demaine, Vida Dujmovic, Pat Morin, Ryuhei Uehara:
Ghost chimneys. CCCG 2010: 63-66 - [c192]Erik D. Demaine, Joseph O'Rourke:
Open problem session. CCCG 2010: 83-86 - [c191]Gill Barequet, Nadia M. Benbernou, David Charlton, Erik D. Demaine, Martin L. Demaine, Mashhood Ishaque, Anna Lubiw, André Schulz, Diane L. Souvaine, Godfried T. Toussaint, Andrew Winslow:
Bounded-degree polyhedronization of point sets. CCCG 2010: 99-102 - [c190]Erik D. Demaine, Martin L. Demaine, Ryuhei Uehara:
Any monotone boolean function can be realized by interlocked polygons. CCCG 2010: 139-142 - [c189]Anna Lubiw, Erik D. Demaine, Martin L. Demaine, Arlo Shallit, Jonah Shallit:
Zipper unfoldings of polyhedral complexes. CCCG 2010: 219-222 - [c188]Erik D. Demaine, Martin L. Demaine, Andrea Hawksley, Hiro Ito, Po-Ru Loh, Shelly Manber, Omari Stephens:
Making Polygons by Simple Folds and One Straight Cut. CGGA 2010: 27-43 - [c187]Greg Aloupis, Prosenjit Bose, Sébastien Collette, Erik D. Demaine, Martin L. Demaine, Karim Douïeb, Vida Dujmovic, John Iacono, Stefan Langerman, Pat Morin:
Common Unfoldings of Polyominoes and Polycubes. CGGA 2010: 44-54 - [c186]Brad Ballinger, Nadia M. Benbernou, Prosenjit Bose, Mirela Damian, Erik D. Demaine, Vida Dujmovic, Robin Y. Flatland, Ferran Hurtado, John Iacono, Anna Lubiw, Pat Morin, Vera Sacristán Adinolfi, Diane L. Souvaine, Ryuhei Uehara:
Coverage with k-Transmitters in the Presence of Obstacles. COCOA (2) 2010: 1-15 - [c185]Tetsuo Asano, Erik D. Demaine, Martin L. Demaine, Ryuhei Uehara:
Kaboozle Is NP-complete, Even in a Strip. FUN 2010: 28-36 - [c184]Erik D. Demaine, Martin L. Demaine, Ryuhei Uehara, Takeaki Uno, Yushi Uno:
UNO Is Hard, Even for a Single Player. FUN 2010: 133-144 - [c183]Greg Aloupis, Jean Cardinal, Sébastien Collette, Erik D. Demaine, Martin L. Demaine, Muriel Dulieu, Ruy Fabila Monroy, Vi Hart, Ferran Hurtado, Stefan Langerman, Maria Saumell, Carlos Seara, Perouz Taslakian:
Matching Points with Things. LATIN 2010: 456-467 - [c182]Neil Gershenfeld, David Dalrymple, Kailiang Chen, Ara N. Knaian, Forrest Green, Erik D. Demaine, Scott Greenwald, Peter Schmidt-Nielsen:
Reconfigurable asynchronous logic automata: (RALA). POPL 2010: 1-6 - [c181]Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi:
Decomposition, Approximation, and Coloring of Odd-Minor-Free Graphs. SODA 2010: 329-344 - [c180]Zachary Abel, Nadia M. Benbernou, Mirela Damian, Erik D. Demaine, Martin L. Demaine, Robin Y. Flatland, Scott Duke Kominers, Robert T. Schweller:
Shape Replication through Self-Assembly and RNase Enzymes. SODA 2010: 1045-1064 - [c179]Gerth Stølting Brodal, Erik D. Demaine, Jeremy T. Fineman, John Iacono, Stefan Langerman, J. Ian Munro:
Cache-Oblivious Dynamic Dictionaries with Update/Query Tradeoffs. SODA 2010: 1448-1456 - [c178]Erik D. Demaine, Morteza Zadimoghaddam:
Scheduling to minimize power consumption using submodular functions. SPAA 2010: 21-29 - [c177]Noga Alon, Erik D. Demaine, MohammadTaghi Hajiaghayi, Tom Leighton:
Basic network creation games. SPAA 2010: 106-113 - [c176]Erik D. Demaine, Morteza Zadimoghaddam:
Minimizing the Diameter of a Network Using Shortcut Edges. SWAT 2010: 420-431 - [c175]Erik D. Demaine, Morteza Zadimoghaddam:
Constant Price of Anarchy in Network Creation Games via Public Service Advertising. WAW 2010: 122-131 - [c174]Erik D. Demaine:
Algorithmic Graph Minors and Bidimensionality. WG 2010: 2 - [e4]Lars Arge, Erik D. Demaine, Raimund Seidel:
Data Structures, 28.02. - 05.03.2010. Dagstuhl Seminar Proceedings 10091, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany 2010 [contents] - [i67]Lars Arge, Erik D. Demaine, Raimund Seidel:
10091 Abstracts Collection - Data Structures. Data Structures 2010 - [i66]Erik D. Demaine, Martin L. Demaine, Ryuhei Uehara, Takeaki Uno, Yushi Uno:
The complexity of UNO. CoRR abs/1003.2851 (2010) - [i65]Erik D. Demaine, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers:
Self-Assembly of Arbitrary Shapes with RNA and DNA tiles (extended abstract). CoRR abs/1004.4383 (2010) - [i64]Oswin Aichholzer, Franz Aurenhammer, Erik D. Demaine, Ferran Hurtado, Pedro Ramos, Jorge Urrutia:
On k-Convex Polygons. CoRR abs/1007.3607 (2010) - [i63]Erik D. Demaine, Sándor P. Fekete, Robert J. Lang:
Circle Packing for Origami Design Is Hard. CoRR abs/1008.1224 (2010) - [i62]Erik D. Demaine, Sándor P. Fekete, Günter Rote, Nils Schweer, Daria Schymura, Mariano Zelke:
Integer Point Sets Minimizing Average Pairwise L1-Distance: What is the Optimal Shape of a Town? CoRR abs/1009.5628 (2010)
2000 – 2009
- 2009
- [b2]Robert A. Hearn, Erik D. Demaine:
Games, puzzles and computation. A K Peters 2009, ISBN 978-1-56881-322-6, pp. I-IX, 1-237 - [j86]Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi:
Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction. Algorithmica 54(2): 142-180 (2009) - [j85]Timothy G. Abbott, Michael A. Burr, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, John Hugg, Daniel Kane, Stefan Langerman, Jelani Nelson, Eynat Rafalin, Kathryn Seyboth, Vincent Yeung:
Dynamic ham-sandwich cuts in the plane. Comput. Geom. 42(5): 419-428 (2009) - [j84]Erik D. Demaine, Francisco Gomez-Martin, Henk Meijer, David Rappaport, Perouz Taslakian, Godfried T. Toussaint, Terry Winograd, David R. Wood:
The distance geometry of music. Comput. Geom. 42(5): 429-454 (2009) - [j83]Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Robin Y. Flatland, Stefan Langerman, Joseph O'Rourke, Suneeta Ramaswami, Vera Sacristán Adinolfi, Stefanie Wuhrer:
Linear reconfiguration of cube-style modular robots. Comput. Geom. 42(6-7): 652-663 (2009) - [j82]Erik D. Demaine, Martin L. Demaine, John Iacono, Stefan Langerman:
Wrapping spheres with flat paper. Comput. Geom. 42(8): 748-757 (2009) - [j81]Hayley N. Iben, James F. O'Brien, Erik D. Demaine:
Refolding Planar Polygons. Discret. Comput. Geom. 41(3): 444-460 (2009) - [j80]Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, Morteza Zadimoghaddam:
The price of anarchy in cooperative network creation games. SIGecom Exch. 8(2): 2 (2009) - [j79]Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveis Gharan, Morteza Zadimoghaddam:
Minimizing movement. ACM Trans. Algorithms 5(3): 30:1-30:30 (2009) - [j78]Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann:
An optimal decomposition algorithm for tree edit distance. ACM Trans. Algorithms 6(1): 2:1-2:19 (2009) - [c173]Erik D. Demaine:
Invited Talk I Actuator Nets: Folding, Reconfiguring and Deploying Sensors. ALGOSENSORS 2009: 1 - [c172]Erik D. Demaine, Joseph O'Rourke:
Open Problems from CCCG 2008. CCCG 2009: 75-78 - [c171]Erik D. Demaine, Sándor P. Fekete, Günter Rote, Nils Schweer, Daria Schymura, Mariano Zelke:
Integer Point Sets Minimizing Average Pairwise l1 Distance: What is the Optimal Shape of a Town? CCCG 2009: 145-148 - [c170]Prosenjit Bose, Jean Cardinal, Sébastien Collette, Erik D. Demaine, Belén Palop, Perouz Taslakian, Norbert Zeh:
Relaxed Gabriel Graphs. CCCG 2009: 169-172 - [c169]Greg Aloupis, Nadia M. Benbernou, Mirela Damian, Erik D. Demaine, Robin Y. Flatland, John Iacono, Stefanie Wuhrer:
Efficient Reconfiguration of Lattice-Based Modular Robots. ECMR 2009: 81-86 - [c168]Erik D. Demaine:
Algorithms Meet Art, Puzzles, and Magic. ESA 2009: 289 - [c167]Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx:
Minimizing Movement: Fixed-Parameter Tractability. ESA 2009: 718-729 - [c166]Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi:
Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs. ICALP (1) 2009: 316-327 - [c165]Erik D. Demaine, MohammadTaghi Hajiaghayi, Philip N. Klein:
Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs. ICALP (1) 2009: 328-340 - [c164]Erik D. Demaine, Gad M. Landau, Oren Weimann:
On Cartesian Trees and Range Minimum Queries. ICALP (1) 2009: 341-353 - [c163]James McLurkin, Erik D. Demaine:
A Distributed boundary detection algorithm for multi-robot systems. IROS 2009: 4791-4798 - [c162]Jean Cardinal, Erik D. Demaine, Martin L. Demaine, Shinji Imahori, Stefan Langerman, Ryuhei Uehara:
Algorithmic Folding Complexity. ISAAC 2009: 452-461 - [c161]Erik D. Demaine, Martin L. Demaine, Goran Konjevod, Robert J. Lang:
Folding a Better Checkerboard. ISAAC 2009: 1074-1083 - [c160]Alan Brunton, Stefanie Wuhrer, Chang Shu, Prosenjit Bose, Erik D. Demaine:
Filling holes in triangular meshes by curve unfolding. Shape Modeling International 2009: 66-72 - [c159]Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane, Mihai Patrascu:
The geometry of binary search trees. SODA 2009: 496-505 - [c158]Ken-ichi Kawarabayashi, Erik D. Demaine, MohammadTaghi Hajiaghayi:
Additive approximation algorithms for list-coloring minor-closed class of graphs. SODA 2009: 1166-1175 - [c157]Glencora Borradaile, Erik D. Demaine, Siamak Tazari:
Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs. STACS 2009: 171-182 - [c156]Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, Morteza Zadimoghaddam:
The Price of Anarchy in Cooperative Network Creation Games. STACS 2009: 301-312 - [c155]Brad Ballinger, David Charlton, Erik D. Demaine, Martin L. Demaine, John Iacono, Ching-Hao Liu, Sheung-Hung Poon:
Minimal Locked Trees. WADS 2009: 61-73 - [c154]Erik D. Demaine:
Algorithms Meet Art, Puzzles, and Magic. WADS 2009: 193 - [c153]Takehiro Ito, Marcin Kaminski, Erik D. Demaine:
Reconfiguration of List Edge-Colorings in a Graph. WADS 2009: 375-386 - [c152]Daniel Kane, Gregory N. Price, Erik D. Demaine:
A Pseudopolynomial Algorithm for Alexandrov's Theorem. WADS 2009: 435-446 - [c151]Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Ilan Newman, Oren Weimann:
The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs. WINE 2009: 125-136 - [e3]Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx:
Parameterized complexity and approximation algorithms, 13.12. - 17.12.2009. Dagstuhl Seminar Proceedings 09511, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany 2009 [contents] - [i61]Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx:
09511 Abstracts Collection - Parameterized complexity and approximation algorithms. Parameterized complexity and approximation algorithms 2009 - [i60]Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx:
09511 Executive Summary - Parameterized complexity and approximation algorithms. Parameterized complexity and approximation algorithms 2009 - [i59]Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx:
09511 Open Problems - Parameterized complexity and approximation algorithms. Parameterized complexity and approximation algorithms 2009 - [i58]Daniel Kane, Gregory Nathan Price, Erik D. Demaine:
A Pseudopolynomial Algorithm for Alexandrov's Theorem. Computational Geometry 2009 - [i57]Timothy G. Abbott, Erik D. Demaine, Blaise Gassend:
A Generalized Carpenter's Rule Theorem for Self-Touching Linkages. CoRR abs/0901.1322 (2009) - [i56]Glencora Borradaile, Erik D. Demaine, Siamak Tazari:
Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs. CoRR abs/0902.1043 (2009) - [i55]Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, Morteza Zadimoghaddam:
The Price of Anarchy in Cooperative Network Creation Games. CoRR abs/0902.1400 (2009) - [i54]Erik D. Demaine, Martin L. Demaine, Vi Hart, John Iacono, Stefan Langerman, Joseph O'Rourke:
Continuous Blooming of Convex Polyhedra. CoRR abs/0906.2461 (2009) - [i53]Erik D. Demaine, Martin L. Demaine, Vi Hart, Gregory N. Price, Tomohiro Tachi:
(Non)existence of Pleated Folds: How Paper Folds Between Creases. CoRR abs/0906.4747 (2009) - [i52]Greg Aloupis, Sébastien Collette, Erik D. Demaine, Stefan Langerman, Vera Sacristán, Stefanie Wuhrer:
Reconfiguration of 3D Crystalline Robots Using O(log n) Parallel Moves. CoRR abs/0908.2440 (2009) - [i51]Greg Aloupis, Erik D. Demaine, Martin L. Demaine, Vida Dujmovic, John Iacono:
Minimum feature size preserving decompositions. CoRR abs/0908.2493 (2009) - [i50]Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Ilan Newman, Oren Weimann:
The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs. CoRR abs/0909.3221 (2009) - [i49]Nadia M. Benbernou, Erik D. Demaine, Martin L. Demaine, Aviv Ovadya:
A Universal Crease Pattern for Folding Orthogonal Shapes. CoRR abs/0909.5388 (2009) - [i48]Hee-Kap Ahn, Sang Won Bae, Erik D. Demaine, Martin L. Demaine, Sang-Sub Kim, Matias Korman, Iris Reinbacher, Wanbin Son:
Covering Points by Disjoint Boxes with Outliers. CoRR abs/0910.1643 (2009) - 2008
- [j77]Ilya Baran, Erik D. Demaine, Dmitriy A. Katz:
Optimally Adaptive Integration of Univariate Lipschitz Functions. Algorithmica 50(2): 255-278 (2008) - [j76]Michael A. Bender, David P. Bunde, Erik D. Demaine, Sándor P. Fekete, Vitus J. Leung, Henk Meijer, Cynthia A. Phillips:
Communication-Aware Processor Allocation for Supercomputers: Finding Point Sets of Small Average Distance. Algorithmica 50(2): 279-298 (2008) - [j75]Ilya Baran, Erik D. Demaine, Mihai Patrascu:
Subquadratic Algorithms for 3SUM. Algorithmica 50(4): 584-596 (2008) - [j74]Erik D. Demaine, MohammadTaghi Hajiaghayi:
The Bidimensionality Theory and Its Algorithmic Applications. Comput. J. 51(3): 292-302 (2008) - [j73]Erik D. Demaine, MohammadTaghi Hajiaghayi:
Linearity of grid minors in treewidth with applications through bidimensionality. Comb. 28(1): 19-36 (2008) - [j72]Greg Aloupis, Erik D. Demaine, Stefan Langerman, Pat Morin, Joseph O'Rourke, Ileana Streinu, Godfried T. Toussaint:
Edge-unfolding nested polyhedral bands. Comput. Geom. 39(1): 30-42 (2008) - [j71]Erik D. Demaine, Jeff Erickson, Danny Krizanc, Henk Meijer, Pat Morin, Mark H. Overmars, Sue Whitesides:
Realizing partitions respecting full and partial order information. J. Discrete Algorithms 6(1): 51-58 (2008) - [j70]Takehiro Ito, Erik D. Demaine, Xiao Zhou, Takao Nishizeki:
Approximability of partitioning graphs with supply and demand. J. Discrete Algorithms 6(4): 627-650 (2008) - [j69]Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Mashhood Ishaque, Eynat Rafalin, Robert T. Schweller, Diane L. Souvaine:
Staged self-assembly: nanomanufacture of arbitrary shapes with O (1) glues. Nat. Comput. 7(3): 347-370 (2008) - [j68]Erik D. Demaine, Uriel Feige, MohammadTaghi Hajiaghayi, Mohammad R. Salavatipour:
Combination Can Be Hard: Approximability of the Unique Coverage Problem. SIAM J. Comput. 38(4): 1464-1483 (2008) - [j67]Noga Alon, Mihai Badoiu, Erik D. Demaine, Martin Farach-Colton, Mohammad Taghi Hajiaghayi, Anastasios Sidiropoulos:
Ordinal embeddings of minimum relaxation: General properties, trees, and ultrametrics. ACM Trans. Algorithms 4(4): 46:1-46:21 (2008) - [c150]Mihai Badoiu, Erik D. Demaine, MohammadTaghi Hajiaghayi, Anastasios Sidiropoulos, Morteza Zadimoghaddam:
Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction. APPROX-RANDOM 2008: 21-34 - [c149]Erik D. Demaine, Martin L. Demaine, Vi Hart:
Computational Balloon Twisting: The Theory of Balloon Polyhedra. CCCG 2008 - [c148]Erik D. Demaine, Robert A. Hearn:
Constraint Logic: A Uniform Framework for Modeling Computation as Games. CCC 2008: 149-162 - [c147]Timothy G. Abbott, Zachary Abel, David Charlton, Erik D. Demaine, Martin L. Demaine, Scott Duke Kominers:
Hinged dissections exist. SCG 2008: 110-119 - [c146]Jun-geun Park, Erik D. Demaine, Seth J. Teller:
Moving-Baseline Localization. IPSN 2008: 15-26 - [c145]Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, Yushi Uno:
On the Complexity of Reconfiguration Problems. ISAAC 2008: 28-39 - [c144]Greg Aloupis, Sébastien Collette, Erik D. Demaine, Stefan Langerman, Vera Sacristán Adinolfi, Stefanie Wuhrer:
Reconfiguration of Cube-Style Modular Robots Using O(logn) Parallel Moves. ISAAC 2008: 342-353 - [c143]Erik D. Demaine:
Algorithmic Graph Minors and Bidimensionality. IWPEC 2008: 9 - [c142]Erik D. Demaine, Stefan Langerman, Eric Price:
Confluently Persistent Tries for Efficient Version Control. SWAT 2008: 160-172 - [c141]Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Dania El-Khechen, Robin Y. Flatland, Stefan Langerman, Joseph O'Rourke, Val Pinciu, Suneeta Ramaswami, Vera Sacristán Adinolfi, Stefanie Wuhrer:
Realistic Reconfiguration of Crystalline (and Telecube) Robots. WAFR 2008: 433-447 - [r3]Erik D. Demaine, MohammadTaghi Hajiaghayi:
Approximation Schemes for Planar Graph Problems. Encyclopedia of Algorithms 2008 - [r2]Erik D. Demaine, MohammadTaghi Hajiaghayi:
Bidimensionality. Encyclopedia of Algorithms 2008 - [i47]David Charlton, Erik D. Demaine, Martin L. Demaine, Gregory N. Price, Yaa-Lirng Tu:
A Locked Orthogonal Tree. CoRR abs/0801.4405 (2008) - [i46]Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Mashhood Ishaque, Eynat Rafalin, Robert T. Schweller, Diane L. Souvaine:
Staged Self-Assembly:Nanomanufacture of Arbitrary Shapes with O(1) Glues. CoRR abs/0803.0316 (2008) - [i45]Zachary Abel, David Charlton, Sébastien Collette, Erik D. Demaine, Martin L. Demaine, Stefan Langerman, Joseph O'Rourke, Val Pinciu, Godfried T. Toussaint:
Cauchy's Arm Lemma on a Growing Sphere. CoRR abs/0804.0986 (2008) - [i44]Daniel Kane, Gregory N. Price, Erik D. Demaine:
A Pseudopolynomial Algorithm for Alexandrov's Theorem. CoRR abs/0812.5030 (2008) - 2007
- [b1]Erik D. Demaine, Joseph O'Rourke:
Geometric folding algorithms - linkages, origami, polyhedra. Cambridge University Press 2007, pp. I-XIII, 1-472 - [j66]Prosenjit Bose, Erik D. Demaine, Ferran Hurtado, John Iacono, Stefan Langerman, Pat Morin:
Geodesic Ham-Sandwich Cuts. Discret. Comput. Geom. 37(3): 325-339 (2007) - [j65]MohammadHossein Bateni, Erik D. Demaine, MohammadTaghi Hajiaghayi, Mohammad Moharrami:
Plane Embeddings of Planar Graph Metrics. Discret. Comput. Geom. 38(3): 615-637 (2007) - [j64]Erik D. Demaine, Mohammad Taghi Hajiaghayi:
Quickly deciding minor-closed parameters in general graphs. Eur. J. Comb. 28(1): 311-314 (2007) - [j63]Erik D. Demaine, Martin L. Demaine:
Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity. Graphs Comb. 23(Supplement-1): 195-208 (2007) - [j62]Sergio Cabello, Erik D. Demaine, Günter Rote:
Planar Embeddings of Graphs with Specified Edge Lengths. J. Graph Algorithms Appl. 11(1): 259-276 (2007) - [j61]Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley, J. Ian Munro:
An Optimal Cache-Oblivious Priority Queue and Its Application to Graph Algorithms. SIAM J. Comput. 36(6): 1672-1695 (2007) - [j60]Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu:
Dynamic Optimality - Almost. SIAM J. Comput. 37(1): 240-251 (2007) - [j59]Erik D. Demaine, John Iacono, Stefan Langerman:
Retroactive data structures. ACM Trans. Algorithms 3(2): 13 (2007) - [j58]Mihai Badoiu, Richard Cole, Erik D. Demaine, John Iacono:
A unified access bound on comparison-based dynamic dictionaries. Theor. Comput. Sci. 382(2): 86-96 (2007) - [c140]Nadia M. Benbernou, Erik D. Demaine, Martin L. Demaine, Michael Hoffmann, Mashhood Ishaque, Diane L. Souvaine, Csaba D. Tóth:
Disjoint Segments Have Convex Partitions with 2-Edge Connected Dual Graphs. CCCG 2007: 13-16 - [c139]Greg Aloupis, Brad Ballinger, Prosenjit Bose, Mirela Damian, Erik D. Demaine, Martin L. Demaine, Robin Y. Flatland, Ferran Hurtado, Stefan Langerman, Joseph O'Rourke, Perouz Taslakian, Godfried T. Toussaint:
Vertex Pops and Popturns. CCCG 2007: 137-140 - [c138]Kevin Buchin, Maike Buchin, Erik D. Demaine, Martin L. Demaine, Dania El-Khechen, Sándor P. Fekete, Christian Knauer, André Schulz, Perouz Taslakian:
On Rolling Cube Puzzles. CCCG 2007: 141-144 - [c137]Erik D. Demaine, Joseph O'Rourke:
Open Problems from CCCG 2006. CCCG 2007: 277-280 - [c136]Erik D. Demaine, Mihai Patrascu:
Tight bounds for dynamic convex hull queries (again). SCG 2007: 354-363 - [c135]Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Mashhood Ishaque, Eynat Rafalin, Robert T. Schweller, Diane L. Souvaine:
Staged Self-assembly: Nanomanufacture of Arbitrary Shapes with O (1) Glues. DNA 2007: 1-14 - [c134]Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann:
An Optimal Decomposition Algorithm for Tree Edit Distance. ICALP 2007: 146-157 - [c133]Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Robin Y. Flatland, Stefan Langerman, Joseph O'Rourke, Suneeta Ramaswami, Vera Sacristán Adinolfi, Stefanie Wuhrer:
Linear Reconfiguration of Cube-Style Modular Robots. ISAAC 2007: 208-219 - [c132]Erik D. Demaine, Martin L. Demaine, Thomas Fevens, Antonio Mesa, Michael A. Soss, Diane L. Souvaine, Perouz Taslakian, Godfried T. Toussaint:
Deflating the Pentagon. KyotoCGGT 2007: 56-67 - [c131]Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, Morteza Zadimoghaddam:
The price of anarchy in network creation games. PODC 2007: 292-298 - [c130]Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveis Gharan, Morteza Zadimoghaddam:
Minimizing movement. SODA 2007: 258-267 - [c129]Erik D. Demaine, Mohammad Taghi Hajiaghayi, Bojan Mohar:
Approximation algorithms via contraction decomposition. SODA 2007: 278-287 - [c128]Erik D. Demaine, Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Amin S. Sayedi-Roshkhar, Morteza Zadimoghaddam:
Scheduling to minimize gaps and power consumption. SPAA 2007: 46-54 - [c127]Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, Oren Weimann:
The Stackelberg Minimum Spanning Tree Game. WADS 2007: 64-76 - [c126]Ajay Deshpande, Taejung Kim, Erik D. Demaine, Sanjay E. Sarma:
A Pseudopolynomial Time O (log n )-Approximation Algorithm for Art Gallery Problems. WADS 2007: 163-174 - [e2]Erik D. Demaine, Gregory Z. Gutin, Dániel Marx, Ulrike Stege:
Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs, 08.07. - 13.07.2007. Dagstuhl Seminar Proceedings 07281, Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany 2007 [contents] - [i43]Erik D. Demaine, Gregory Z. Gutin, Dániel Marx, Ulrike Stege:
07281 Abstracts Collection -- Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs 2007 - [i42]Erik D. Demaine, Gregory Z. Gutin, Dániel Marx, Ulrike Stege:
07281 Open Problems -- Structure Theory and FPT Algorithmcs for Graphs, Digraphs and Hypergraphs. Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs 2007 - [i41]Erik D. Demaine, Francisco Gomez-Martin, Henk Meijer, David Rappaport, Perouz Taslakian, Godfried T. Toussaint, Terry Winograd, David R. Wood:
The Distance Geometry of Music. CoRR abs/0705.4085 (2007) - [i40]Gregory N. Price, Erik D. Demaine:
Generalized D-Forms Have No Spurious Creases. CoRR abs/0711.2605 (2007) - [i39]Timothy G. Abbott, Zachary Abel, David Charlton, Erik D. Demaine, Martin L. Demaine, Scott Duke Kominers:
Hinged Dissections Exist. CoRR abs/0712.2094 (2007) - [i38]Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, Oren Weimann:
The Stackelberg Minimum Spanning Tree Game. CoRR abs/cs/0703019 (2007) - 2006
- [j57]Erik D. Demaine, Stefan Langerman, Joseph O'Rourke:
Geometric Restrictions on Producible Polygonal Protein Chains. Algorithmica 44(2): 167-181 (2006) - [j56]Ben Leong, Barbara Liskov, Erik D. Demaine:
EpiChord: Parallelizing the Chord lookup algorithm with reactive routing state management. Comput. Commun. 29(9): 1243-1259 (2006) - [j55]Mihai Badoiu, Erik D. Demaine, Mohammad Taghi Hajiaghayi, Piotr Indyk:
Low-Dimensional Embedding with Extra Information. Discret. Comput. Geom. 36(4): 609-632 (2006) - [j54]Erik D. Demaine, Martin L. Demaine, Arthur Langerman, Stefan Langerman:
Morpion Solitaire. Theory Comput. Syst. 39(3): 439-453 (2006) - [j53]Erik D. Demaine, Martin L. Demaine:
Puzzles, Art, and Magic with Algorithms. Theory Comput. Syst. 39(3): 473-481 (2006) - [j52]Mihai Patrascu, Erik D. Demaine:
Logarithmic Lower Bounds in the Cell-Probe Model. SIAM J. Comput. 35(4): 932-963 (2006) - [j51]Erik D. Demaine, MohammadTaghi Hajiaghayi, Dimitrios M. Thilikos:
The Bidimensional Theory of Bounded-Genus Graphs. SIAM J. Discret. Math. 20(2): 357-371 (2006) - [j50]Erik D. Demaine, Dotan Emanuel, Amos Fiat, Nicole Immorlica:
Correlation clustering in general weighted graphs. Theor. Comput. Sci. 361(2-3): 172-187 (2006) - [j49]Erik D. Demaine, Sándor P. Fekete, Shmuel Gal:
Online searching with turn cost. Theor. Comput. Sci. 361(2-3): 342-355 (2006) - [c125]Mirela Damian, Erik D. Demaine, Martin L. Demaine, Vida Dujmovic, Dania El-Khechen, Robin Y. Flatland, John Iacono, Stefan Langerman, Henk Meijer, Suneeta Ramaswami, Diane L. Souvaine, Perouz Taslakian, Godfried T. Toussaint:
Curves in the Sand: Algorithmic Drawing. CCCG 2006 - [c124]Erik D. Demaine:
Paul Erdos Memorial Lecture: Linkage Folding: From Erdos to Proteins. CCCG 2006 - [c123]Erik D. Demaine, Blaise Gassend, Joseph O'Rourke, Godfried T. Toussaint:
Polygons Flip Finitely: Flaws and a Fix. CCCG 2006 - [c122]Erik D. Demaine, Joseph O'Rourke:
Open Problems: Open Problems from CCCG 2005. CCCG 2006 - [c121]Sachio Teramoto, Erik D. Demaine, Ryuhei Uehara:
Voronoi game on graphs and its complexity. CIG 2006: 265-271 - [c120]Robert Connelly, Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Stefan Langerman, Joseph S. B. Mitchell, Ares Ribó, Günter Rote:
Locked and unlocked chains of planar shapes. SCG 2006: 61-70 - [c119]Hayley N. Iben, James F. O'Brien, Erik D. Demaine:
Refolding planar polygons. SCG 2006: 71-79 - [c118]MohammadHossein Bateni, Mohammad Taghi Hajiaghayi, Erik D. Demaine, Mohammad Moharrami:
Plane embeddings of planar graph metrics. SCG 2006: 197-206 - [c117]Erik D. Demaine:
Origami, Linkages, and Polyhedra: Folding with Algorithms. ESA 2006: 1 - [c116]David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Perouz Taslakian:
Necklaces, Convolutions, and X + Y. ESA 2006: 160-171 - [c115]Erik D. Demaine, Mohammad Taghi Hajiaghayi, Ken-ichi Kawarabayashi:
Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction. ISAAC 2006: 3-15 - [c114]Takehiro Ito, Erik D. Demaine, Xiao Zhou, Takao Nishizeki:
Approximability of Partitioning Graphs with Supply and Demand. ISAAC 2006: 121-130 - [c113]Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, Michiel H. M. Smid:
Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams. LATIN 2006: 80-92 - [c112]Ilya Baran, Erik D. Demaine, Dmitriy A. Katz:
Optimally Adaptive Integration of Univariate Lipschitz Functions. LATIN 2006: 142-153 - [c111]Erik D. Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh, Mihai Patrascu:
De Dictionariis Dynamicis Pauco Spatio Utentibus (lat. On Dynamic Dictionaries Using Little Space). LATIN 2006: 349-361 - [c110]Erik D. Demaine, Mohammad Taghi Hajiaghayi, Uriel Feige, Mohammad R. Salavatipour:
Combination can be hard: approximability of the unique coverage problem. SODA 2006: 162-171 - [c109]Micah Adler, Erik D. Demaine, Nicholas J. A. Harvey, Mihai Patrascu:
Lower bounds for asymmetric communication channels and distributed source coding. SODA 2006: 251-260 - [i37]Robert Connelly, Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Stefan Langerman, Joseph S. B. Mitchell, Ares Ribó, Günter Rote:
Locked and Unlocked Chains of Planar Shapes. CoRR abs/cs/0604022 (2006) - [i36]Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann:
An O(n^3)-Time Algorithm for Tree Edit Distance. CoRR abs/cs/0604037 (2006) - 2005
- [j48]Gerth Stølting Brodal, Erik D. Demaine, J. Ian Munro:
Fast allocation and deallocation with an improved buddy system. Acta Informatica 41(4-5): 273-291 (2005) - [j47]Erik D. Demaine, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos:
Exponential Speedup of Fixed-Parameter Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors. Algorithmica 41(4): 245-267 (2005) - [j46]David Benoit, Erik D. Demaine, J. Ian Munro, Rajeev Raman, Venkatesh Raman, S. Srinivasa Rao:
Representing Trees of Higher Degree. Algorithmica 43(4): 275-292 (2005) - [j45]Erik D. Demaine, Martin L. Demaine, David Eppstein, Greg N. Frederickson, Erich Friedman:
Hinged dissection of polyominoes and polyforms. Comput. Geom. 31(3): 237-262 (2005) - [j44]David Bremner, Erik D. Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, Godfried T. Toussaint:
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries. Discret. Comput. Geom. 33(4): 593-604 (2005) - [j43]Ilya Baran, Erik D. Demaine:
Optimal Adaptive Algorithms for Finding the nearest and Farthest Point on a Parametric Black-box Curve. Int. J. Comput. Geom. Appl. 15(4): 327-350 (2005) - [j42]Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, Mark H. Overmars, Sue Whitesides:
Separating Point Sets in Polygonal Environments. Int. J. Comput. Geom. Appl. 15(4): 403-420 (2005) - [j41]Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos:
Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM 52(6): 866-893 (2005) - [j40]Michael A. Bender, Erik D. Demaine, Martin Farach-Colton:
Cache-Oblivious B-Trees. SIAM J. Comput. 35(2): 341-358 (2005) - [j39]Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sándor P. Fekete, Joseph S. B. Mitchell, Saurabh Sethia:
Optimal Covering Tours with Turn Costs. SIAM J. Comput. 35(3): 531-566 (2005) - [j38]Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos:
Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs. ACM Trans. Algorithms 1(1): 33-47 (2005) - [j37]Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, Suneeta Ramaswami, Saurabh Sethia, Jorge Urrutia:
Games on triangulations. Theor. Comput. Sci. 343(1-2): 42-71 (2005) - [j36]Robert A. Hearn, Erik D. Demaine:
PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theor. Comput. Sci. 343(1-2): 72-96 (2005) - [c108]Timothy G. Abbott, Erik D. Demaine, Martin L. Demaine, Daniel Kane, Stefan Langerman, Jelani Nelson, Vincent Yeung:
Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane. CCCG 2005: 61-64 - [c107]Erik D. Demaine, Francisco Gomez-Martin, Henk Meijer, David Rappaport, Perouz Taslakian, Godfried T. Toussaint, Terry Winograd, David R. Wood:
The Distance Geometry of Deep Rhythms and Scales. CCCG 2005: 163-166 - [c106]Erik D. Demaine, Stefan Langerman:
Optimizing a 2D Function Satisfying Unimodality Properties. ESA 2005: 887-898 - [c105]Erik D. Demaine, Mohammad Taghi Hajiaghayi, Ken-ichi Kawarabayashi:
Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring. FOCS 2005: 637-646 - [c104]Nissanka Bodhi Priyantha, Hari Balakrishnan, Erik D. Demaine, Seth J. Teller:
Mobile-assisted localization in wireless sensor networks. INFOCOM 2005: 172-183 - [c103]Jonathan Bredin, Erik D. Demaine, Mohammad Taghi Hajiaghayi, Daniela Rus:
Deploying sensor networks with guaranteed capacity and fault tolerance. MobiHoc 2005: 309-319 - [c102]Erik D. Demaine, Mohammad Taghi Hajiaghayi:
Bidimensionality: new connections between FPT algorithms and PTASs. SODA 2005: 590-601 - [c101]Noga Alon, Mihai Badoiu, Erik D. Demaine, Martin Farach-Colton, Mohammad Taghi Hajiaghayi, Anastasios Sidiropoulos:
Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics. SODA 2005: 650-659 - [c100]Erik D. Demaine, Mohammad Taghi Hajiaghayi:
Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality. SODA 2005: 682-689 - [c99]Michael A. Bender, David P. Bunde, Erik D. Demaine, Sándor P. Fekete, Vitus J. Leung, Henk Meijer, Cynthia A. Phillips:
Communication-Aware Processor Allocation for Supercomputers. WADS 2005: 169-181 - [c98]Erik D. Demaine, Martin L. Demaine, Jeffrey F. Lindy, Diane L. Souvaine:
Hinged Dissection of Polypolyhedra. WADS 2005: 205-217 - [c97]Ilya Baran, Erik D. Demaine, Mihai Patrascu:
Subquadratic Algorithms for 3SUM. WADS 2005: 409-421 - [e1]Lars Arge, Michael A. Bender, Erik D. Demaine, Charles E. Leiserson, Kurt Mehlhorn:
Cache-Oblivious and Cache-Aware Algorithms, 18.07. - 23.07.2004. Dagstuhl Seminar Proceedings 04301, IBFI, Schloss Dagstuhl, Germany 2005 [contents] - [i35]Mihai Patrascu, Erik D. Demaine:
Logarithmic Lower Bounds in the Cell-Probe Model. CoRR abs/cs/0502041 (2005) - [i34]Erik D. Demaine, MohammadTaghi Hajiaghayi:
Bidimensionality, Map Graphs, and Grid Minors. CoRR abs/cs/0502070 (2005) - [i33]Erik D. Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh, Mihai Patrascu:
De Dictionariis Dynamicis Pauco Spatio Utentibus. CoRR abs/cs/0512081 (2005) - [i32]Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, Michiel H. M. Smid:
Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams. CoRR abs/cs/0512091 (2005) - 2004
- [j35]Erik D. Demaine, Mohammad Taghi Hajiaghayi:
Diameter and Treewidth in Minor-Closed Graph Families, Revisited. Algorithmica 40(3): 211-215 (2004) - [j34]Erik D. Demaine, John Iacono, Stefan Langerman:
Proximate point searching. Comput. Geom. 28(1): 29-40 (2004) - [j33]Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Joseph S. B. Mitchell, Saurabh Sethia, Steven Skiena:
When can you fold a map? Comput. Geom. 29(1): 23-46 (2004) - [j32]Therese Biedl, Timothy M. Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai J. Golin, James A. King, J. Ian Munro:
Fun-Sort--or the chaos of unordered binary search. Discret. Appl. Math. 144(3): 231-236 (2004) - [j31]Therese Biedl, Erik D. Demaine, Christian A. Duncan, Rudolf Fleischer, Stephen G. Kobourov:
Tight bounds on maximal and maximum matchings. Discret. Math. 285(1-3): 7-15 (2004) - [j30]Ron Breukelaar, Erik D. Demaine, Susan Hohenberger, Hendrik Jan Hoogeboom, Walter A. Kosters, David Liben-Nowell:
Tetris is hard, even to approximate. Int. J. Comput. Geom. Appl. 14(1-2): 41-68 (2004) - [j29]Erik D. Demaine, Mohammad Taghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos:
Approximation algorithms for classes of graphs excluding single-crossing graphs as minors. J. Comput. Syst. Sci. 69(2): 166-195 (2004) - [j28]Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos:
Bidimensional Parameters and Local Treewidth. SIAM J. Discret. Math. 18(3): 501-511 (2004) - [j27]Therese Biedl, Brona Brejová, Erik D. Demaine, Angèle M. Hamel, Alejandro López-Ortiz, Tomás Vinar:
Finding hidden independent sets in interval graphs. Theor. Comput. Sci. 310(1-3): 287-307 (2004) - [j26]Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer:
Solitaire Clobber. Theor. Comput. Sci. 313(3): 325-338 (2004) - [j25]Erik D. Demaine, Rudolf Fleischer, Aviezri S. Fraenkel, Richard J. Nowakowski:
Appendix B: Open problems at the 2002 Dagstuhl Seminar on Algorithmic Combinatorial Game Theory. Theor. Comput. Sci. 313(3): 539-543 (2004) - [c96]Greg Aloupis, Erik D. Demaine, Stefan Langerman, Pat Morin, Joseph O'Rourke, Ileana Streinu, Godfried T. Toussaint:
Unfolding polyhedral bands. CCCG 2004: 60-63 - [c95]Erik D. Demaine, Satyan L. Devadoss, Joseph S. B. Mitchell, Joseph O'Rourke:
Continuous foldability of polygonal paper. CCCG 2004: 64-67 - [c94]Prosenjit Bose, Erik D. Demaine, Ferran Hurtado, John Iacono, Stefan Langerman, Pat Morin:
Geodesic ham-sandwich cuts. SCG 2004: 1-9 - [c93]Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, Mark H. Overmars, Sue Whitesides:
Separating point sets in polygonal environments. SCG 2004: 10-16 - [c92]Jason H. Cantarella, Erik D. Demaine, Hayley N. Iben, James F. O'Brien:
An energy-driven approach to linkage unfolding. SCG 2004: 134-143 - [c91]Ilya Baran, Erik D. Demaine:
Optimal adaptive algorithms for finding the nearest and farthest point on a parametric black-box curve. SCG 2004: 220-229 - [c90]Mihai Badoiu, Erik D. Demaine, Mohammad Taghi Hajiaghayi, Piotr Indyk:
Low-dimensional embedding with extra information. SCG 2004: 320-329 - [c89]Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu:
Dynamic Optimality - Almost. FOCS 2004: 484-490 - [c88]Erik D. Demaine, Mohammad Taghi Hajiaghayi:
Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth. GD 2004: 517-533 - [c87]Ben Leong, Barbara Liskov, Erik D. Demaine:
EpiChord: parallelizing the chord lookup algorithm with reactive routing state management. ICON 2004: 270-276 - [c86]Erik D. Demaine:
Puzzles, Art, and Magic with Algorithms. ISAAC 2004: 1 - [c85]Erik D. Demaine, John Iacono, Stefan Langerman:
Grid Vertex-Unfolding Orthostacks. JCDCG 2004: 76-82 - [c84]Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos:
Bidimensional Parameters and Local Treewidth. LATIN 2004: 109-118 - [c83]Mihai Badoiu, Erik D. Demaine:
A Simplified, Dynamic Unified Structure. LATIN 2004: 466-473 - [c82]Erik D. Demaine, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos:
The Bidimensional Theory of Bounded-Genus Graphs. MFCS 2004: 191-203 - [c81]Hayley N. Iben, James F. O'Brien, Erik D. Demaine:
Refolding planar polygons. SIGGRAPH Sketches 2004: 94 - [c80]Mihai Patrascu, Erik D. Demaine:
Tight bounds for the partial-sums problem. SODA 2004: 20-29 - [c79]Erik D. Demaine, John Iacono, Stefan Langerman:
Retroactive data structures. SODA 2004: 281-290 - [c78]Erik D. Demaine, Thouis R. Jones, Mihai Patrascu:
Interpolation search for non-independent data. SODA 2004: 529-530 - [c77]Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos:
Subexponential parameterized algorithms on graphs of bounded-genus and H-minor-free graphs. SODA 2004: 830-839 - [c76]Erik D. Demaine, Mohammad Taghi Hajiaghayi:
Equivalence of local treewidth and linear local treewidth and its algorithmic applications. SODA 2004: 840-849 - [c75]Lukasz Golab, David DeHaan, Alejandro López-Ortiz, Erik D. Demaine:
Finding Frequent Items in Sliding Windows with Multinomially-Distributed Item Frequencies. SSDBM 2004: 425-426 - [c74]Mihai Patrascu, Erik D. Demaine:
Lower bounds for dynamic connectivity. STOC 2004: 546-553 - [r1]Robert Connelly, Erik D. Demaine:
Geometry and Topology of Polygonal Linkages. Handbook of Discrete and Computational Geometry, 2nd Ed. 2004: 197-218 - [i31]Lars Arge, Michael A. Bender, Erik D. Demaine, Charles E. Leiserson, Kurt Mehlhorn:
04301 Abstracts Collection - Cache-Oblivious and Cache-Aware Algorithms. Cache-Oblivious and Cache-Aware Algorithms 2004 - [i30]Erik D. Demaine, Sándor P. Fekete, Shmuel Gal:
Online Searching with Turn Cost. CoRR cs.DS/0406045 (2004) - [i29]Michael A. Bender, David P. Bunde, Erik D. Demaine, Sándor P. Fekete, Vitus J. Leung, Henk Meijer, Cynthia A. Phillips:
Communication-Aware Processor Allocation for Supercomputers. CoRR cs.DS/0407058 (2004) - [i28]Erik D. Demaine, John Iacono, Stefan Langerman:
Worst-Case Optimal Tree Layout in a Memory Hierarchy. CoRR cs.DS/0410048 (2004) - 2003
- [j24]Ziv Bar-Joseph, Erik D. Demaine, David K. Gifford, Nathan Srebro, Angèle M. Hamel, Tommi S. Jaakkola:
K-ary Clustering with Optimal Leaf Ordering for Gene Expression Data. Bioinform. 19(9): 1070-1078 (2003) - [j23]Marshall W. Bern, Erik D. Demaine, David Eppstein, Eric Kuo, Andrea Mantler, Jack Snoeyink:
Ununfoldable polyhedra with convex faces. Comput. Geom. 24(2): 51-62 (2003) - [j22]Oswin Aichholzer, David Bremner, Erik D. Demaine, Henk Meijer, Vera Sacristán, Michael A. Soss:
Long proteins with unique optimal foldings in the H-P model. Comput. Geom. 25(1-2): 139-159 (2003) - [j21]Erik D. Demaine, Martin L. Demaine, Michael Hoffmann, Joseph O'Rourke:
Pushing blocks is hard. Comput. Geom. 26(1): 21-36 (2003) - [j20]Erik D. Demaine, Stefan Langerman, Joseph O'Rourke, Jack Snoeyink:
Interlocked open and closed linkages with few joints. Comput. Geom. 26(1): 37-45 (2003) - [j19]Robert Connelly, Erik D. Demaine, Günter Rote:
Straightening Polygonal Arcs and Convexifying Polygonal Cycles. Discret. Comput. Geom. 30(2): 205-239 (2003) - [j18]Erik D. Demaine, Alejandro López-Ortiz:
A linear lower bound on index size for text retrieval. J. Algorithms 48(1): 2-15 (2003) - [j17]Therese Biedl, Jonathan F. Buss, Erik D. Demaine, Martin L. Demaine, Mohammad Taghi Hajiaghayi, Tomás Vinar:
Palindrome recognition using a multidimensional tape. Theor. Comput. Sci. 302(1-3): 475-480 (2003) - [j16]Erik D. Demaine, Alejandro López-Ortiz, J. Ian Munro:
On universally easy classes for NP-complete problems. Theor. Comput. Sci. 304(1-3): 471-476 (2003) - [c73]Erik D. Demaine:
Open Problems from ALENEX 2003. ALENEX 2003 - [c72]Robert A. Hearn, Erik D. Demaine, Greg N. Frederickson:
Hinged Dissection of Polygons is Hard. CCCG 2003: 98-102 - [c71]Erik D. Demaine, Jeff Erickson, Stefan Langerman:
On the Complexity of Halfspace Volume Queries. CCCG 2003: 159-160 - [c70]Therese Biedl, Brona Brejová, Erik D. Demaine, Angèle M. Hamel, Alejandro López-Ortiz, Tomás Vinar:
Finding Hidden Independent Sets in Interval Graphs. COCOON 2003: 182-191 - [c69]Erik D. Demaine, Susan Hohenberger, David Liben-Nowell:
Tetris is Hard, Even to Approximate. COCOON 2003: 351-363 - [c68]Therese Biedl, Erik D. Demaine, Alexander Golynski, Joseph Douglas Horton, Alejandro López-Ortiz, Guillaume Poirier, Claude-Guy Quimper:
Optimal Dynamic Video-on-Demand Using Adaptive Broadcasting. ESA 2003: 90-101 - [c67]Sergio Cabello, Erik D. Demaine, Günter Rote:
Planar Embeddings of Graphs with Specified Edge Lengths. GD 2003: 283-294 - [c66]Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos:
Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs. ICALP 2003: 829-844 - [c65]Lukasz Golab, David DeHaan, Erik D. Demaine, Alejandro López-Ortiz, J. Ian Munro:
Identifying frequent items in sliding windows over on-line packet streams. Internet Measurement Conference 2003: 173-178 - [c64]Erik D. Demaine, Stefan Langerman, Joseph O'Rourke:
Geometric Restrictions on Producible Polygonal Protein Chains. ISAAC 2003: 395-404 - [c63]Erik D. Demaine, Nicole Immorlica:
Correlation Clustering with Partial Information. RANDOM-APPROX 2003: 1-13 - [c62]Nissanka Bodhi Priyantha, Hari Balakrishnan, Erik D. Demaine, Seth J. Teller:
Anchor-free distributed localization in sensor networks. SenSys 2003: 340-341 - [c61]David Bremner, Erik D. Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, Godfried T. Toussaint:
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries. WADS 2003: 451-461 - [i27]Ilya Baran, Erik D. Demaine:
Optimal Adaptive Algorithms for Finding the Nearest and Farthest Point on a Parametric Black-Box Curve. CoRR cs.CG/0307005 (2003) - [i26]Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sándor P. Fekete, Joseph S. B. Mitchell, Saurabh Sethia:
Optimal Covering Tours with Turn Costs. CoRR cs.DS/0309014 (2003) - 2002
- [j15]Therese Biedl, Erik D. Demaine, Martin L. Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Steve Robbins, Ileana Streinu, Godfried T. Toussaint, Sue Whitesides:
A note on reconfiguring tree linkages: trees can lock. Discret. Appl. Math. 117(1-3): 293-297 (2002) - [j14]Oswin Aichholzer, Carmen Cortés, Erik D. Demaine, Vida Dujmovic, Jeff Erickson, Henk Meijer, Mark H. Overmars, Belén Palop, Suneeta Ramaswami, Godfried T. Toussaint:
Flipturning Polygons. Discret. Comput. Geom. 28(2): 231-253 (2002) - [j13]Therese C. Biedl, Eowyn Cenek, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Ming-wei Wang:
Balanced k-colorings. Discret. Math. 254(1-3): 19-32 (2002) - [j12]Erik D. Demaine, Martin L. Demaine, Anna Lubiw, Joseph O'Rourke:
Enumerating Foldings and Unfoldings Between Polygons and Polytopes. Graphs Comb. 18(1): 93-104 (2002) - [j11]Prosenjit Bose, Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, Alejandro López-Ortiz, Pat Morin, J. Ian Munro:
Online Routing in Convex Subdivisions. Int. J. Comput. Geom. Appl. 12(4): 283-296 (2002) - [c60]Erik D. Demaine, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos:
-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor. APPROX 2002: 67-80 - [c59]Erik D. Demaine, John Iacono, Stefan Langerman:
Proximate point searching. CCCG 2002: 1-4 - [c58]Greg Aloupis, Erik D. Demaine, Henk Meijer, Joseph O'Rourke, Ileana Streinu, Godfried T. Toussaint:
On flat-state connectivity of chains with fixed acute angles. CCCG 2002: 27-30 - [c57]Erik D. Demaine, Robert A. Hearn, Michael Hoffmann:
Push-2-f is pspace-complete. CCCG 2002: 31-35 - [c56]Greg Aloupis, Prosenjit Bose, Erik D. Demaine, Stefan Langerman, Henk Meijer, Mark H. Overmars, Godfried T. Toussaint:
Computing signed permutations of polygons. CCCG 2002: 68-71 - [c55]Therese Biedl, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Paul Nijjar, Ryuhei Uehara, Ming-wei Wang:
Tighter bounds on the genus of nonorthogonal polyhedra built from rectangles. CCCG 2002: 105-108 - [c54]Erik D. Demaine, Joseph O'Rourke:
Open problems from cccg 2001. CCCG 2002 - [c53]Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer:
Solitaire Clobber. Computers and Games 2002: 188-200 - [c52]Erik D. Demaine, Stefan Langerman, Joseph O'Rourke, Jack Snoeyink:
Interlocked open linkages with few joints. SCG 2002: 189-198 - [c51]Erik D. Demaine, David Eppstein, Jeff Erickson, George W. Hart, Joseph O'Rourke:
Vertex-unfoldings of simplicial manifolds. SCG 2002: 237-243 - [c50]Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton:
Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy. ESA 2002: 139-151 - [c49]Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, Jack Zito:
Two Simplified Algorithms for Maintaining Order in a List. ESA 2002: 152-164 - [c48]Michael A. Bender, Erik D. Demaine, Martin Farach-Colton:
Efficient Tree Layout in a Multilevel Memory Hierarchy. ESA 2002: 165-173 - [c47]Erik D. Demaine, Alejandro López-Ortiz, J. Ian Munro:
Frequency Estimation of Internet Packet Streams with Limited Space. ESA 2002: 348-360 - [c46]Robert A. Hearn, Erik D. Demaine:
The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications. ICALP 2002: 401-413 - [c45]Erik D. Demaine, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos:
Exponential Speedup of Fixed-Parameter Algorithms on K3, 3-Minor-Free or K5-Minor-Free Graphs. ISAAC 2002: 262-273 - [c44]Greg Aloupis, Erik D. Demaine, Vida Dujmovic, Jeff Erickson, Stefan Langerman, Henk Meijer, Joseph O'Rourke, Mark H. Overmars, Michael A. Soss, Ileana Streinu, Godfried T. Toussaint:
Flat-State Connectivity of Linkages under Dihedral Motions. ISAAC 2002: 369-380 - [c43]Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, Suneeta Ramaswami, Saurabh Sethia, Jorge Urrutia:
Playing with Triangulations. JCDCG 2002: 22-37 - [c42]Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley, J. Ian Munro:
Cache-oblivious priority queue and graph algorithm applications. STOC 2002: 268-276 - [c41]Erik D. Demaine, Alejandro López-Ortiz, J. Ian Munro:
Robot Localization without Depth Perception. SWAT 2002: 249-259 - [c40]Ziv Bar-Joseph, Erik D. Demaine, David K. Gifford, Angèle M. Hamel, Tommi S. Jaakkola, Nathan Srebro:
K-ary Clustering with Optimal Leaf Ordering for Gene Expression Data. WABI 2002: 506-520 - [i25]Robert A. Hearn, Erik D. Demaine:
PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation. CoRR cs.CC/0205005 (2002) - [i24]Erik D. Demaine, Susan Hohenberger, David Liben-Nowell:
Tetris is Hard, Even to Approximate. CoRR cs.CC/0210020 (2002) - [i23]Oswin Aichholzer, David Bremner, Erik D. Demaine, Henk Meijer, Vera Sacristán, Michael A. Soss:
Long Proteins with Unique Optimal Foldings in the H-P Model. CoRR cs.CG/0201018 (2002) - [i22]Erik D. Demaine, Joseph O'Rourke:
Open Problems from CCCG 2002. CoRR cs.CG/0212050 (2002) - [i21]Erik D. Demaine, Martin L. Demaine, Helena A. Verrill:
Coin-Moving Puzzles. CoRR cs.DM/0204002 (2002) - [i20]Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer:
Solitaire Clobber. CoRR cs.DM/0204017 (2002) - [i19]Stephen Alstrup, Michael A. Bender, Erik D. Demaine, Martin Farach-Colton, J. Ian Munro, Theis Rauhe, Mikkel Thorup:
Efficient Tree Layout in a Multilevel Memory Hierarchy. CoRR cs.DS/0211010 (2002) - 2001
- [j10]Erik D. Demaine, Martin L. Demaine, Craig S. Kaplan:
Polygons cuttable by a circular saw. Comput. Geom. 20(1-2): 69-84 (2001) - [j9]Oswin Aichholzer, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, Mark H. Overmars, Michael A. Soss, Godfried T. Toussaint:
Reconfiguring convex polygons. Comput. Geom. 20(1-2): 85-95 (2001) - [j8]Therese Biedl, Erik D. Demaine, Martin L. Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Mark H. Overmars, Steve Robbins, Ileana Streinu, Godfried T. Toussaint, Sue Whitesides:
Locked and Unlocked Polygonal Chains in Three Dimensions. Discret. Comput. Geom. 26(3): 269-281 (2001) - [j7]Therese C. Biedl, Prosenjit Bose, Erik D. Demaine, Anna Lubiw:
Efficient Algorithms for Petersen's Matching Theorem. J. Algorithms 38(1): 110-134 (2001) - [j6]Erik D. Demaine, Ian T. Foster, Carl Kesselman, Marc Snir:
Generalized Communicators in the Message Passing Interface. IEEE Trans. Parallel Distributed Syst. 12(6): 610-616 (2001) - [c39]Erik D. Demaine, Alejandro López-Ortiz, J. Ian Munro:
Experiments on Adaptive Set Intersections for Text Retrieval Systems. ALENEX 2001: 91-104 - [c38]Erik D. Demaine, Martin L. Demaine, Anna Lubiw:
The cccg 2001 logo. CCCG 2001 - [c37]Erik D. Demaine, Michael Hoffmann:
Pushing blocks is np-complete for noncrossing solution paths. CCCG 2001: 65-68 - [c36]Erik D. Demaine, Stefan Langerman, Joseph O'Rourke:
Short interlocked linkages. CCCG 2001: 69-72 - [c35]Erik D. Demaine, Joseph S. B. Mitchell:
Reaching folded states of a rectangular piece of paper. CCCG 2001: 73-75 - [c34]Erik D. Demaine, Joseph O'Rourke:
Open problems from cccg 2000. CCCG 2001: 185-187 - [c33]Therese Biedl, Erik D. Demaine, Christian A. Duncan, Rudolf Fleischer, Stephen G. Kobourov:
Tight Bounds on Maximal and Maximum Matchings. ISAAC 2001: 308-319 - [c32]Erik D. Demaine:
Playing Games with Algorithms: Algorithmic Combinatorial Game Theory. MFCS 2001: 18-32 - [c31]Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sándor P. Fekete, Joseph S. B. Mitchell, Saurabh Sethia:
Optimal covering tours with turn costs. SODA 2001: 138-147 - [c30]Erik D. Demaine, Alejandro López-Ortiz:
A linear lower bound on index size for text retrieval. SODA 2001: 289-294 - [c29]Erik D. Demaine, Alejandro López-Ortiz, J. Ian Munro:
On universally easy classes for NP-complete problems. SODA 2001: 910-911 - [c28]Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Joseph S. B. Mitchell, Saurabh Sethia, Steven Skiena:
When Can You Fold a Map? WADS 2001: 401-413 - [i18]Erik D. Demaine:
Playing Games with Algorithms: Algorithmic Combinatorial Game Theory. CoRR cs.CC/0106019 (2001) - [i17]Therese C. Biedl, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Lars Jacobsen, J. Ian Munro:
The Complexity of Clickomania. CoRR cs.CC/0107031 (2001) - [i16]Erik D. Demaine, David Eppstein, Jeff Erickson, George W. Hart, Joseph O'Rourke:
Vertex-Unfoldings of Simplicial Polyhedra. CoRR cs.CG/0107023 (2001) - [i15]Erik D. Demaine, Martin L. Demaine, Anna Lubiw, Joseph O'Rourke:
Enumerating Foldings and Unfoldings between Polygons and Polytopes. CoRR cs.CG/0107024 (2001) - [i14]Erik D. Demaine, David Eppstein, Jeff Erickson, George W. Hart, Joseph O'Rourke:
Vertex-Unfoldings of Simplicial Manifolds. CoRR cs.CG/0110054 (2001) - 2000
- [j5]Erik D. Demaine, Martin L. Demaine, Joseph S. B. Mitchell:
Folding flat silhouettes and wrapping polyhedral packages: New results in computational origami. Comput. Geom. 16(1): 3-21 (2000) - [j4]Erik D. Demaine, Joseph O'Rourke:
Computational Geometry Column 37. Int. J. Comput. Geom. Appl. 10(1): 103-107 (2000) - [c27]Oswin Aichholzer, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, Mark H. Overmars, Michael A. Soss, Godfried T. Toussaint:
Reconfiguring Convex Polygons. CCCG 2000 - [c26]Erik D. Demaine, Martin L. Demaine, Craig S. Kaplan:
Polygons Cuttable by a Circular Saw. CCCG 2000 - [c25]Erik D. Demaine, Martin L. Demaine, Joseph O'Rourke:
PushPush and Push-1 are NP-hard in 2D. CCCG 2000 - [c24]Erik D. Demaine, Joseph O'Rourke:
Session O1: Open Problems and Planning. CCCG 2000 - [c23]Michael A. Bender, Erik D. Demaine, Martin Farach-Colton:
Cache-Oblivious B-Trees. FOCS 2000: 399-409 - [c22]Robert Connelly, Erik D. Demaine, Günter Rote:
Straighting Polygonal Arcs and Convexifying Polygonal Cycles. FOCS 2000: 432-442 - [c21]Prosenjit Bose, Pat Morin, Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, J. Ian Munro, Alejandro López-Ortiz:
Online Routing in Convex Subdivisions. ISAAC 2000: 47-59 - [c20]Erik D. Demaine:
Folding and Unfolding Linkages, Paper, and Polyhedra. JCDCG 2000: 113-124 - [c19]Therese C. Biedl, Eowyn Cenek, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Ming-wei Wang:
Balanced k-Colorings. MFCS 2000: 202-211 - [c18]Erik D. Demaine, Alejandro López-Ortiz, J. Ian Munro:
Adaptive set intersections, unions, and differences. SODA 2000: 743-752 - [i13]Robert Connelly, Erik D. Demaine, Günter Rote:
Every Polygon Can Be Untangled. EuroCG 2000: 62-65 - [i12]Erik D. Demaine, Martin L. Demaine, David Eppstein:
Phutball Endgames are Hard. CoRR cs.CC/0008025 (2000) - [i11]Erik D. Demaine, Martin L. Demaine, Joseph O'Rourke:
PushPush is NP-hard in 2D. CoRR cs.CG/0001019 (2000) - [i10]Erik D. Demaine, Martin L. Demaine, Anna Lubiw, Joseph O'Rourke:
Examples, Counterexamples, and Enumeration Results for Foldings and Unfoldings between Polygons and Polytopes. CoRR cs.CG/0007019 (2000) - [i9]Erik D. Demaine, Martin L. Demaine, Joseph O'Rourke:
PushPush and Push-1 are NP-hard in 2D. CoRR cs.CG/0007021 (2000) - [i8]Oswin Aichholzer, Carmen Cortés, Erik D. Demaine, Vida Dujmovic, Jeff Erickson, Henk Meijer, Mark H. Overmars, Belén Palop, Suneeta Ramaswami, Godfried T. Toussaint:
Flipturning polygons. CoRR cs.CG/0008010 (2000) - [i7]Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Joseph S. B. Mitchell, Saurabh Sethia, Steven Skiena:
When Can You Fold a Map? CoRR cs.CG/0011026 (2000)
1990 – 1999
- 1999
- [j3]Erik D. Demaine, Joseph O'Rourke:
Computational geometry column 37. SIGACT News 30(3): 39-42 (1999) - [c17]Marshall W. Bern, Erik D. Demaine, David Eppstein, Eric Kuo:
Ununfoldable polyhedra. CCCG 1999 - [c16]Erik D. Demaine, Martin L. Demaine, David Eppstein, Erich Friedman:
Hinged dissections of polyominoes and polyforms. CCCG 1999 - [c15]Erik D. Demaine, Martin L. Demaine, Joseph S. B. Mitchell:
Folding Flat Silhouettes and Wrapping Polyhedral Packages: New Results in Computational Origami. SCG 1999: 105-114 - [c14]Erik D. Demaine, Martin L. Demaine, Anna Lubiw, Joseph O'Rourke, Irena Pashchenko:
Metamorphosis of the Cube. SCG 1999: 409-410 - [c13]Erik D. Demaine, J. Ian Munro:
Fast Allocation and Deallocation with an Improved Buddy System. FSTTCS 1999: 84-96 - [c12]Therese C. Biedl, Erik D. Demaine, Sylvain Lazard, Steven M. Robbins, Michael A. Soss:
Convexifying Monotone Polygons. ISAAC 1999: 415-424 - [c11]Therese C. Biedl, Prosenjit Bose, Erik D. Demaine, Anna Lubiw:
Efficient Algorithms for Petersen's Matching Theorem. SODA 1999: 130-139 - [c10]Therese Biedl, Erik D. Demaine, Martin L. Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Mark H. Overmars, Steve Robbins, Ileana Streinu, Godfried T. Toussaint, Sue Whitesides:
Locked and Unlocked Polygonal Chains in 3D. SODA 1999: 866-867 - [c9]Erik D. Demaine, Martin L. Demaine, Anna Lubiw:
Folding and One Straight Cut Suffice. SODA 1999: 891-892 - [c8]Andrej Brodnik, Svante Carlsson, Erik D. Demaine, J. Ian Munro, Robert Sedgewick:
Resizable Arrays in Optimal Time and Space. WADS 1999: 37-48 - [c7]David Benoit, Erik D. Demaine, J. Ian Munro, Venkatesh Raman:
Representing Trees of Higer Degree. WADS 1999: 169-180 - [i6]Erik D. Demaine, Martin L. Demaine, David Eppstein, Greg N. Frederickson, Erich Friedman:
Hinged Dissection of Polyominoes and Polyforms. CoRR cs.CG/9907018 (1999) - [i5]Marshall W. Bern, Erik D. Demaine, David Eppstein, Eric Kuo, Andrea Mantler, Jack Snoeyink:
Ununfoldable Polyhedra with Convex Faces. CoRR cs.CG/9908003 (1999) - [i4]Erik D. Demaine, Joseph O'Rourke:
Computational Geometry Column 37. CoRR cs.CG/9908007 (1999) - [i3]Therese Biedl, Erik D. Demaine, Martin L. Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Mark H. Overmars, Steve Robbins, Ileana Streinu, Godfried T. Toussaint, Sue Whitesides:
Locked and Unlocked Polygonal Chains in 3D. CoRR cs.CG/9910009 (1999) - [i2]Therese Biedl, Erik D. Demaine, Martin L. Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Steve Robbins, Ileana Streinu, Godfried T. Toussaint, Sue Whitesides:
On Reconfiguring Tree Linkages: Trees can Lock. CoRR cs.CG/9910024 (1999) - 1998
- [j2]Erik D. Demaine:
C to Java: Converting Pointers into References. Concurr. Pract. Exp. 10(11-13): 851-861 (1998) - [c6]Therese Biedl, Erik D. Demaine, Martin L. Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Steve Robbins, Ileana Streinu, Godfried T. Toussaint, Sue Whitesides:
On reconfiguring tree linkages: Trees can lock. CCCG 1998 - [c5]Therese Biedl, Erik D. Demaine, Martin L. Demaine, Anna Lubiw, Mark H. Overmars, Joseph O'Rourke, Steve Robbins, Sue Whitesides:
Unfolding some classes of orthogonal polyhedra. CCCG 1998 - [c4]Therese C. Biedl, Erik D. Demaine, Martin L. Demaine, Anna Lubiw, Godfried T. Toussaint:
Hiding disks in folded polygons. CCCG 1998 - [c3]Erik D. Demaine, Martin L. Demaine:
Planar Drawings of Origami Polyhedra. GD 1998: 438-440 - [c2]Erik D. Demaine:
Protocols for Non-Deterministic Communication over Synchronous Channels. IPPS/SPDP 1998: 24-30 - [c1]Erik D. Demaine, Martin L. Demaine, Anna Lubiw:
Folding and Cutting Paper. JCDCG 1998: 104-118 - [i1]Therese Biedl, Erik D. Demaine, Martin L. Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Mark H. Overmars, Steve Robbins, Ileana Streinu, Godfried T. Toussaint, Sue Whitesides:
Locked and Unlocked Polygonal Chains in 3D. CoRR cs.CG/9811019 (1998) - 1996
- [j1]Erik D. Demaine, Sampalli Srinivas:
A Novel Routing Algorithm for k-Ary n-Cube Interconnection Networks. Int. J. High Speed Comput. 8(1): 81-92 (1996)
Coauthor Index
aka: Vera Sacristán
aka: Therese C. Biedl
aka: Dylan H. Hendrickson
aka: Adam C. Hesterberg
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from , , and to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-12-17 21:50 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint