☰

Erik D. Demaine, Ph.D. - Publications

Affiliations: 
Massachusetts Institute of Technology, Cambridge, MA, United States 
 Tufts University, Boston 
Area:
Mathematics, Computer Science
Tree Info Similar researchers PubMed Report error

151 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2020 Abel Z, Bosboom J, Coulombe M, Demaine ED, Hamilton L, Hesterberg A, Kopinsky J, Lynch J, Rudoy M, Thielen C. Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible Theoretical Computer Science. 839: 41-102. DOI: 10.1016/J.Tcs.2020.05.031  0.453
2020 Cardinal J, Demaine ED, Eppstein D, Hearn RA, Winslow A. Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect Theoretical Computer Science. 806: 332-343. DOI: 10.1016/J.Tcs.2019.05.028  0.415
2020 Benbernou NM, Demaine ED, Demaine ML, Lubiw A. Universal hinge patterns for folding strips efficiently into any grid polyhedron Computational Geometry: Theory and Applications. 89: 101633. DOI: 10.1016/J.Comgeo.2020.101633  0.602
2020 Akitaya HA, Avery C, Bergeron J, Demaine ED, Kopinsky J, Ku JS. Infinite All-Layers Simple Foldability Graphs and Combinatorics. 36: 231-244. DOI: 10.1007/S00373-019-02079-2  0.332
2020 Demaine ED, Iacono J, Koumoutsos G, Langerman S. Belga B-Trees Theory of Computing Systems \/ Mathematical Systems Theory. 1-18. DOI: 10.1007/S00224-020-09991-8  0.321
2019 Demaine ED, Reidl F, Rossmanith P, Villaamil FS, Sikdar S, Sullivan BD. Structural sparsity of complex networks: Bounded expansion in random models and real-world graphs Journal of Computer and System Sciences. 105: 199-241. DOI: 10.1016/J.Jcss.2019.05.004  0.432
2019 Becker AT, Demaine ED, Fekete SP, Lonsford J, Morris-Wright R. Particle computation: complexity, algorithms, and logic Natural Computing. 18: 181-201. DOI: 10.1007/S11047-017-9666-6  0.324
2018 Abel Z, Alvarez V, Demaine ED, Fekete SP, Gour A, Hesterberg A, Keldenich P, Scheffer C. Conflict-Free Coloring of Graphs Siam Journal On Discrete Mathematics. 32: 2675-2702. DOI: 10.1137/17M1146579  0.383
2018 An B, Miyashita S, Ong A, Tolley MT, Demaine ML, Demaine ED, Wood RJ, Rus D. An End-to-End Approach to Self-Folding Origami Structures Ieee Transactions On Robotics. 34: 1409-1424. DOI: 10.1109/Tro.2018.2862882  0.34
2018 Demaine ED, Rudoy M. A simple proof that the (n2 − 1)-puzzle is hard Theoretical Computer Science. 732: 80-84. DOI: 10.1016/J.Tcs.2018.04.031  0.397
2018 Demaine ED, Ma F, Schvartzman A, Waingarten E, Aaronson S. The fewest clues problem Theoretical Computer Science. 748: 28-39. DOI: 10.1016/J.Tcs.2018.01.020  0.403
2017 Bosboom JW, Demaine ED, Demaine ML, Hesterberg AC, Manurangsi P, Yodpinyanee A. Even 1 × n Edge-Matching and Jigsaw Puzzles are Really Hard Journal of Information Processing. 25: 682-694. DOI: 10.2197/Ipsjjip.25.682  0.333
2017 Demaine ED, Ganesan V, Kontsevoi V, Liu Q, Liu QC, Ma F, Nachum O, Sidford A, Waingarten E, Ziegler D. Arboral Satisfaction: Recognition and LP Approximation Information Processing Letters. 127: 1-5. DOI: 10.1016/J.Ipl.2017.04.012  0.417
2016 Bateni M, Hajiaghayi M, Demaine ED, Marx D. A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting Proceedings of the Annual Acm Symposium On Theory of Computing. 19: 570-583. DOI: 10.1145/2897518.2897549  0.311
2015 Ku JS, Demaine ED. Folding flat crease patterns with thick materials Proceedings of the Asme Design Engineering Technical Conference. 5. DOI: 10.1115/1.4031954  0.337
2015 Demaine ED, Demaine ML, Fox-Epstein E, Hoang DA, Ito T, Ono H, Otachi Y, Uehara R, Yamada T. Linear-time algorithm for sliding tokens on trees Theoretical Computer Science. 600: 132-142. DOI: 10.1016/J.Tcs.2015.07.037  0.448
2015 Demaine ED, Demaine ML. Fun with fonts Theoretical Computer Science. 586: 111-119. DOI: 10.1016/J.Tcs.2015.01.054  0.365
2015 Demaine ED, Eppstein D, Hesterberg A, Ito H, Lubiw A, Uehara R, Uno Y. Folding a paper strip to minimize thickness Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8973: 113-124. DOI: 10.1016/J.Jda.2015.09.003  0.654
2014 Abel Z, Demaine ED, Demaine ML, Eppstein D, Lubiw A, Uehara R. Flat foldings of plane graphs with prescribed angles and edge lengths Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8871: 272-283. DOI: 10.20382/Jocg.V9I1A3  0.714
2014 Aichholzer O, Aloupis G, Demaine ED, Demaine ML, Fekete SP, Hoffmann M, Lubiw A, Snoeyink J, Winslow A. Covering Folded Shapes Journal of Computational Geometry. 5: 150-167. DOI: 10.20382/Jocg.V5I1A8  0.645
2014 Abel Z, Demaine ED, Demaine ML, Horiyama T, Uehara R. Computational complexity of piano-hinged dissections Ieice Transactions On Fundamentals of Electronics, Communications and Computer Sciences. 1206-1212. DOI: 10.1587/Transfun.E97.A.1206  0.352
2014 Demaine ED, Hajiaghayi M, Marx D. Minimizing movement: Fixed-parameter tractability Acm Transactions On Algorithms. 11. DOI: 10.1145/2650247  0.668
2014 Demaine ED, Hajiaghayi M, Klein PN. Node-weighted steiner tree and group steiner tree in planar graphs Acm Transactions On Algorithms. 10. DOI: 10.1145/2601070  0.726
2014 Abel Z, Demaine ED, Demaine ML, Itoh JI, Lubiw A, Nara C, O'Rourke J. Continuously flattening polyhedra using straight skeletons Proceedings of the Annual Symposium On Computational Geometry. 396-405. DOI: 10.1145/2582112.2582171  0.665
2014 Alon N, Demaine ED, Hajiaghayi M, Kanellopoulos P, Leighton T. Correction: Basic network creation games Siam Journal On Discrete Mathematics. 28: 1638-1640. DOI: 10.1137/140955343  0.721
2014 Abel ZR, Demaine ED, Demaine ML, Ito H, Snoeyink J, Uehara R. Bumpy pyramid folding 26th Canadian Conference On Computational Geometry, Cccg 2014. 258-266. DOI: 10.1016/J.Comgeo.2018.06.007  0.423
2014 Demaine ED, Demaine ML, Itoh JI, Lubiw A, Nara C, O'Rourke J. Reprint of: Refold rigidity of convex polyhedra Computational Geometry: Theory and Applications. 47: 507-517. DOI: 10.1016/J.Comgeo.2013.11.001  0.664
2014 Ito T, Demaine ED. Approximability of the subset sum reconfiguration problem Journal of Combinatorial Optimization. 28: 639-654. DOI: 10.1007/s10878-012-9562-z  0.331
2014 Bremner D, Chan TM, Demaine ED, Erickson JJ, Hurtado F, Iacono JJ, Langerman S, Pǎtraşcu M, Taslakian P. Necklaces, Convolutions, and X+Y Algorithmica. 69: 294-314. DOI: 10.1007/S00453-012-9734-3  0.373
2014 Borradaile G, Demaine ED, Tazari S. Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs Algorithmica. 68: 287-311. DOI: 10.1007/S00453-012-9662-2  0.404
2014 Damian M, Demaine ED, Flatland R. Unfolding Orthogonal Polyhedra with Quadratic Refinement: The Delta-Unfolding Algorithm Graphs and Combinatorics. 30: 125-140. DOI: 10.1007/s00373-012-1257-9  0.315
2014 Demaine ED, Demaine ML, Minsky YN, Mitchell JSB, Rivest RL, Pătraşcu M. Picture-hanging puzzles Theory of Computing Systems. 54: 531-550. DOI: 10.1007/S00224-013-9501-0  0.329
2013 Abel Z, Demaine ED, Demaine ML, Eisenstat S, Lubiw A, Schulz A, Souvainek DL, Viglietta G, Winslowk A. Algorithms for designing pop-up cards Leibniz International Proceedings in Informatics, Lipics. 20: 269-280. DOI: 10.4230/LIPIcs.STACS.2013.269  0.603
2013 Abel Z, Demaine ED, Demaine ML, Eisenstat S, Lynch J, Schardl TB. Finding a Hamiltonian path in a cube with specified turns is hard Journal of Information Processing. 21: 368-377. DOI: 10.2197/Ipsjjip.21.368  0.357
2013 Abel Z, Demaine ED, Demaine ML, Eisenstat S, Lynch J, Schardl TB, Shapiro-Ellowitz I. Folding equilateral plane graphs International Journal of Computational Geometry and Applications. 23: 75-92. DOI: 10.1142/S0218195913600017  0.458
2013 Butler S, Demaine ED, Graham RL, Tachi T. Constructing Points Through Folding And Intersection International Journal of Computational Geometry and Applications. 23: 49-64. DOI: 10.1142/S0218195913500039  0.319
2013 Alon N, Demaine ED, Hajiaghayi MT, Leighton T. Basic network creation games Siam Journal On Discrete Mathematics. 27: 656-668. DOI: 10.1137/090771478  0.402
2013 Sung C, Demaine ED, Demaine ML, Rus D. Edge-compositions of 3D surfaces Journal of Mechanical Design, Transactions of the Asme. 135. DOI: 10.1115/1.4025378  0.334
2013 Demaine ED, Demaine ML, Itoh JI, Lubiw A, Nara C, Oêrourke J. Refold rigidity of convex polyhedra Computational Geometry: Theory and Applications. 46: 979-989. DOI: 10.1016/J.Comgeo.2013.05.002  0.63
2013 Aloupis G, Cardinal J, Collette S, Demaine ED, Demaine ML, Dulieu M, Fabila-Monroy R, Hart V, Hurtado F, Langerman S, Saumell M, Seara C, Taslakian P. Non-crossing matchings of points with geometric objects Computational Geometry: Theory and Applications. 46: 78-92. DOI: 10.1016/J.Comgeo.2012.04.005  0.37
2013 Barequet G, Benbernou N, Charlton D, Demaine ED, Demaine ML, Ishaque M, Lubiw A, Schulz A, Souvaine DL, Toussaint GT, Winslow A. Bounded-degree polyhedronization of point sets Computational Geometry: Theory and Applications. 46: 148-153. DOI: 10.1016/J.Comgeo.2012.02.008  0.605
2013 Demaine ED, Ghodsi M, Hajiaghayi M, Sayedi-Roshkhar AS, Zadimoghaddam M. Scheduling to minimize gaps and power consumption Journal of Scheduling. 16: 151-160. DOI: 10.1007/S10951-012-0309-6  0.673
2013 Ballinger B, Benbernou N, Bose P, Damian M, Demaine ED, Dujmović V, Flatland R, Hurtado F, Iacono J, Lubiw A, Morin P, Sacristán V, Souvaine D, Uehara R. Coverage with k-transmitters in the presence of obstacles Journal of Combinatorial Optimization. 25: 208-233. DOI: 10.1007/S10878-012-9475-X  0.556
2013 Cardinal J, Demaine ED, Fiorini S, Joret G, Newman I, Weimann O. The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs Journal of Combinatorial Optimization. 25: 19-46. DOI: 10.1007/s10878-011-9414-2  0.341
2013 Aichholzer O, Aloupis G, Demaine ED, Demaine ML, Fekete ͆P, Hoffmann M, Lubiw A, Snoeyink J, Winslow A. Covering folded shapes Cccg 2013 - 25th Canadian Conference On Computational Geometry. 73-78.  0.614
2012 Demaine ED, Demaine ML, Uehara R. Any monotone function is realized by interlocked polygons Algorithms. 5: 148-157. DOI: 10.3390/A5010148  0.344
2012 Asano T, Demaine ED, Demaine ML, Uehara R. NP-completeness of generalized Kaboozle Journal of Information Processing. 20: 713-718. DOI: 10.2197/Ipsjjip.20.713  0.346
2012 Demaine ED, Hajiaghayi M, Mahini H, Zadimoghaddam M. The price of anarchy in network creation games Acm Transactions On Algorithms. 8: 13. DOI: 10.1145/2151171.2151176  0.669
2012 Aichholzer O, Aurenhammer F, Demaine ED, Hurtado F, Ramos P, Urrutia J. On k-convex polygons Computational Geometry: Theory and Applications. 45: 73-87. DOI: 10.1016/J.Comgeo.2011.09.001  0.415
2012 Abbott TG, Abel Z, Charlton D, Demaine ED, Demaine ML, Kominers SD. Hinged Dissections Exist Discrete and Computational Geometry. 47: 150-186. DOI: 10.1007/S00454-010-9305-9  0.425
2012 Aloupis G, Demaine ED, Demaine ML, Dujmović V, Iacono J. Meshes preserving minimum feature size Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7579: 258-273. DOI: 10.1007/978-3-642-34191-5_25  0.482
2012 Demaine ED, Lubiw A. A generalization of the source unfolding of convex polyhedra Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7579: 185-199. DOI: 10.1007/978-3-642-34191-5_18  0.535
2011 Demaine ED, Hajiaghayi M, Kawarabayashi KI. Contraction decomposition in h-minor-free graphs and algorithmic applications Proceedings of the Annual Acm Symposium On Theory of Computing. 441-450. DOI: 10.1145/1993636.1993696  0.428
2011 Aloupis G, Bose P, Demaine ED, Langerman S, Meijer HH, Overmars MM, Toussaint GG. Computing Signed Permutations Of Polygons International Journal of Computational Geometry and Applications. 21: 87-100. DOI: 10.1142/S0218195911003561  0.427
2011 Cheung KC, Demaine ED, Bachrach JR, Griffith S. Programmable assembly with universally foldable strings (moteins) Ieee Transactions On Robotics. 27: 718-729. DOI: 10.1109/Tro.2011.2132951  0.323
2011 An B, Benbernou N, Demaine ED, Rus D. Planning to fold multiple objects from a single self-folding sheet Robotica. 29: 87-102. DOI: 10.1017/S0263574710000731  0.357
2011 Aloupis G, Collette S, Damian M, Demaine ED, Flatland R, Langerman S, O'Rourke J, Pinciu V, Ramaswami S, Sacristán V, Wuhrer S. Efficient constant-velocity reconfiguration of crystalline robots Robotica. 29: 59-71. DOI: 10.1017/S026357471000072X  0.315
2011 Ito T, Demaine ED, Harvey NJA, Papadimitriou CH, Sideri M, Uehara R, Uno Y. On the complexity of reconfiguration problems Theoretical Computer Science. 412: 1054-1065. DOI: 10.1016/J.Tcs.2010.12.005  0.354
2011 Demaine ED, Fekete SP, Rote G, Schweer N, Schymura D, Zelke M. Integer point sets minimizing average pairwise L1 distance: What is the optimal shape of a town? Computational Geometry: Theory and Applications. 44: 82-94. DOI: 10.1016/J.Comgeo.2010.09.004  0.325
2011 Demaine ED, Demaine ML, Hart V, Price GN, Tachi T. (Non)Existence of Pleated Folds: How Paper Folds Between Creases Graphs and Combinatorics. 27: 377-397. DOI: 10.1007/S00373-011-1025-2  0.315
2011 Demaine ED, Demaine ML, Hart V, Iacono J, Langerman S, O'Rourke J. Continuous Blooming of Convex Polyhedra Graphs and Combinatorics. 27: 363-376. DOI: 10.1007/S00373-011-1024-3  0.332
2011 Cardinal J, Demaine ED, Demaine ML, Imahori S, Ito T, Kiyomi M, Langerman S, Uehara R, Uno T. Algorithmic Folding Complexity Graphs and Combinatorics. 27: 341-351. DOI: 10.1007/S00373-011-1019-0  0.384
2011 Aloupis G, Bose PK, Collette S, Demaine ED, Demaine ML, Douïeb K, Dujmović V, Iacono J, Langerman S, Morin P. Common unfoldings of polyominoes and polycubes Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7033: 44-54. DOI: 10.1007/978-3-642-24983-9_5  0.307
2011 Demaine ED, Demaine ML, Eisenstat S, Lubiw A, Winslow A. Algorithms for solving rubik's cubes Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6942: 689-700. DOI: 10.1007/978-3-642-23719-5_58  0.59
2011 Berman P, Demaine ED, Zadimoghaddam M. O(1)-approximations for maximum movement problems Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6845: 62-74. DOI: 10.1007/978-3-642-22935-0_6  0.349
2010 Hawkes E, An B, Benbernou NM, Tanaka H, Kim S, Demaine ED, Rus D, Wood RJ. Programmable matter by folding. Proceedings of the National Academy of Sciences of the United States of America. 107: 12441-5. PMID 20616049 DOI: 10.1073/Pnas.0914069107  0.315
2010 Bredin JL, Demaine ED, Hajiaghayi MT, Rus D. Deploying sensor networks with guaranteed fault tolerance Ieee/Acm Transactions On Networking. 18: 216-228. DOI: 10.1109/Tnet.2009.2024941  0.309
2010 Demaine ED, Demaine ML, Uehara R, Uno T, Uno Y. UNO is hard, even for a single player Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6099: 133-144. DOI: 10.1016/J.Tcs.2013.11.023  0.369
2010 Connelly R, Demaine ED, Demaine ML, Fekete SPP, Langerman S, Mitchell JSB, Ribó A, Rote G. Locked and Unlocked Chains of Planar Shapes Discrete and Computational Geometry. 44: 439-462. DOI: 10.1007/S00454-010-9262-3  0.333
2010 Demaine ED, Zadimoghaddam M. Minimizing the diameter of a network using shortcut edges Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6139: 420-431. DOI: 10.1007/978-3-642-13731-0_39  0.356
2010 Demaine ED, Hajiaghayi MT, Kawarabayashi KI. Decomposition, approximation, and coloring of odd-minor-free graphs Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 329-344.  0.37
2010 Demaine ED, Demaine ML, Lubiw A, Shallit A, Shallit JL. Zipper unfoldings of polyhedral complexes Proceedings of the 22nd Annual Canadian Conference On Computational Geometry, Cccg 2010. 219-222.  0.593
2009 Demaine ED, Hajiaghayi M, Mahini H, Zadimoghaddam M. The price of anarchy in cooperative network creation games Sigecom Exchanges. 8: 2. DOI: 10.1145/1980522.1980524  0.647
2009 Demaine ED, Mozes S, Rossman B, Weimann O. An optimal decomposition algorithm for tree edit distance Acm Transactions On Algorithms. 6. DOI: 10.1145/1644015.1644017  0.307
2009 Ito T, Kamiński M, Demaine ED. Reconfiguration of list edge-colorings in a graph Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5664: 375-386. DOI: 10.1016/J.Dam.2012.05.014  0.475
2009 Demaine ED, Demaine ML, Iacono J, Langerman S. Wrapping spheres with flat paper Computational Geometry: Theory and Applications. 42: 748-757. DOI: 10.1016/J.Comgeo.2008.10.006  0.302
2009 Abbott TG, Burr MA, Chan TM, Demaine ED, Demaine ML, Hugg J, Kane D, Langerman S, Nelson J, Rafalin E, Seyboth K, Yeung V. Dynamic ham-sandwich cuts in the plane Computational Geometry: Theory and Applications. 42: 419-428. DOI: 10.1016/J.Comgeo.2008.09.008  0.356
2009 Demaine ED, Price GN. Generalized D-forms have no spurious creases Discrete and Computational Geometry. 43: 179-186. DOI: 10.1007/S00454-009-9218-7  0.304
2009 Iben HN, O'Brien JF, Demaine ED. Refolding planar polygons Discrete and Computational Geometry. 41: 444-460. DOI: 10.1007/S00454-009-9145-7  0.374
2009 Demaine ED, Hajiaghayi M, Kawarabayashi K. Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner’s Contraction Algorithmica. 54: 142-180. DOI: 10.1007/S00453-007-9138-Y  0.753
2009 Demaine ED, Landau GM, Weimann O. On cartesian trees and range minimum queries Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5555: 341-353. DOI: 10.1007/978-3-642-02927-1_29  0.3
2009 Demaine ED, Hajiaghayi M, Kawarabayashi KI. Approximation algorithms via structural results for apex-minor-free graphs Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5555: 316-327. DOI: 10.1007/978-3-642-02927-1_27  0.348
2009 Kawarabayashi KI, Demaine ED, Hajiaghayi M. Additive approximation algorithms for list-coloring minor-closed class of graphs Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 1166-1175.  0.386
2009 Demaine ED, Hajiaghayi M, Mahini H, Zadimoghaddam M. The price of anarchy in cooperative network creation games Leibniz International Proceedings in Informatics, Lipics. 3: 301-312.  0.313
2008 Alon N, Bădoiu M, Demaine ED, Farach-Colton M, Hajiaghayi M, Sidiropoulos A. Ordinal embeddings of minimum relaxation: General properties, trees, and ultrametrics Acm Transactions On Algorithms. 4: 46. DOI: 10.1145/1383369.1383377  0.693
2008 Demaine ED, Feige U, Hajiaghayi M, Salavatipour MR. Combination Can Be Hard: Approximability of the Unique Coverage Problem Siam Journal On Computing. 38: 1464-1483. DOI: 10.1137/060656048  0.733
2008 Demaine ED, Hajiaghayi MT. The bidimensionality theory and its algorithmic applications Computer Journal. 51: 292-302. DOI: 10.1093/Comjnl/Bxm033  0.733
2008 Ito T, Demaine ED, Zhou X, Nishizeki T. Approximability of partitioning graphs with supply and demand Journal of Discrete Algorithms. 6: 627-650. DOI: 10.1016/j.jda.2008.03.002  0.322
2008 Demaine ED, Erickson J, Kriz̧anc D, Meijer H, Morin P, Overmars M, Whitesides S. Realizing partitions respecting full and partial order information Journal of Discrete Algorithms. 6: 51-58. DOI: 10.1016/J.Jda.2006.10.004  0.342
2008 Demaine ED, Hajiaghayi M. Linearity of grid minors in treewidth with applications through bidimensionality Combinatorica. 28: 19-36. DOI: 10.1007/S00493-008-2140-4  0.741
2008 Baran I, Demaine ED, Pǎtraşcu M. Subquadratic algorithms for 3SUM Algorithmica (New York). 50: 584-596. DOI: 10.1007/S00453-007-9036-3  0.359
2008 Demaine ED. Algorithmic graph minors and bidimensionality Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5018: 9. DOI: 10.1007/978-3-540-79723-4_2  0.344
2007 Demaine ED, Hajiaghayi MT, Mahini H, Sayedi-Roshkhar AS, Oveisgharan S, Zadimoghaddam M. Minimizing movement Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 7: 258-267. DOI: 10.1145/1541885.1541891  0.708
2007 Arge L, Bender MA, Demaine ED, Holland-Minkley B, Munro JI. An optimal cache-oblivious priority queue and its application to graph algorithms Siam Journal On Computing. 36: 1672-1695. DOI: 10.1137/S0097539703428324  0.532
2007 Demaine ED, Demaine ML, Taslakian P, Toussaint GG. Sand drawings and Gaussian graphs Journal of Mathematics and the Arts. 1: 125-132. DOI: 10.1080/17513470701413451  0.462
2007 Demaine ED, Hajiaghayi M. Quickly deciding minor-closed parameters in general graphs European Journal of Combinatorics. 28: 311-314. DOI: 10.1016/J.Ejc.2005.07.003  0.432
2007 Bateni M, Demaine ED, Hajiaghayi M, Moharrami M. Plane embeddings of planar graph metrics Discrete and Computational Geometry. 38: 615-637. DOI: 10.1007/S00454-007-1353-4  0.755
2007 Demaine ED, Demaine ML. Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity Graphs and Combinatorics. 23: 195-208. DOI: 10.1007/S00373-007-0713-4  0.325
2007 Deshpande A, Kim T, Demaine ED, Sarma SE. A pseudopolynomial time O(log n)-approximation algorithm for art gallery problems Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 4619: 163-174.  0.351
2006 Demaine ED, Feige U, Hajiaghayi MT, Salavatipour MR. Combination can be hard: Approximability of the unique coverage problem Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 162-171. DOI: 10.1145/1109557.1109577  0.366
2006 Pǎtraşcu M, Demaine ED. Logarithmic lower bounds in the cell-probe model Siam Journal On Computing. 35: 932-963. DOI: 10.1137/S0097539705447256  0.436
2006 Demaine ED, Emanuel D, Fiat A, Immorlica N. Correlation clustering in general weighted graphs Theoretical Computer Science. 361: 172-187. DOI: 10.1016/J.Tcs.2006.05.008  0.374
2006 Leong B, Liskov B, Demaine ED. EpiChord: Parallelizing the Chord lookup algorithm with reactive routing state management Computer Communications. 29: 1243-1259. DOI: 10.1016/J.Comcom.2005.10.002  0.355
2006 Badoiu M, Demaine ED, Hajiaghayi M, Indyk P. Low-dimensional embedding with extra information Discrete and Computational Geometry. 36: 609-632. DOI: 10.1007/S00454-006-1268-5  0.731
2006 Demaine ED, Demaine ML. Puzzles, art, and magic with algorithms Theory of Computing Systems. 39: 473-481. DOI: 10.1007/S00224-005-1241-3  0.356
2006 Demaine ED, Hajiaghayi M, Kawarabayashi KI. Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 4288: 3-15. DOI: 10.1007/11940128_3  0.406
2006 Demaine ED. Origami, linkages, and polyhedra: Folding with algorithms Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 4168: 1.  0.302
2005 Demaine ED, Fomin FV, Hajiaghayi M, Thilikos DM. Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs Journal of the Acm. 52: 866-893. DOI: 10.1145/1101821.1101823  0.75
2005 Demaine ED, Fomin FV, Hajiaghayi M, Thilikos DM. Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs Acm Transactions On Algorithms. 1: 33-47. DOI: 10.1145/1077464.1077468  0.734
2005 Demaine ED, Erickson J, Hurtado F, Iacono J, Langerman S, Meijer H, Overmars M, Whitesides S. Separating point sets in polygonal environments International Journal of Computational Geometry and Applications. 15: 403-419. DOI: 10.1142/S0218195905001762  0.358
2005 Arkin EM, Bender MA, Demaine ED, Fekete SP, Mitchell JSB, Sethia S. Optimal covering tours with turn costs Siam Journal On Computing. 35: 531-566. DOI: 10.1137/S0097539703434267  0.322
2005 Demaine ED, Hajiaghayi M, Kawarabayashi KI. Algorithmic graph minor theory: Decomposition, approximation, and coloring Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 2005: 637-646. DOI: 10.1109/SFCS.2005.14  0.392
2005 Hearn RA, Demaine ED. PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation Theoretical Computer Science. 343: 72-96. DOI: 10.1016/J.Tcs.2005.05.008  0.467
2005 Aichholzer O, Bremner D, Demaine ED, Hurtado F, Kranakis E, Krasser H, Ramaswami S, Sethia S, Urrutia J. Games on triangulations Theoretical Computer Science. 343: 42-71. DOI: 10.1016/J.Tcs.2005.05.007  0.322
2005 Demaine ED, Demaine ML, Eppstein D, Frederickson GN, Friedman E. Hinged dissection of polyominoes and polyforms Computational Geometry: Theory and Applications. 31: 237-262. DOI: 10.1016/J.Comgeo.2004.12.008  0.37
2005 Bremner D, Demaine E, Erickson J, Iacono J, Langerman S, Morin P, Toussaint G. Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries Discrete and Computational Geometry. 33: 593-604. DOI: 10.1007/S00454-004-1152-0  0.356
2005 Demaine ED, Hajiaghayi M, Thilikos DM. Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors Algorithmica (New York). 41: 245-267. DOI: 10.1007/S00453-004-1125-Y  0.502
2005 Demaine ED, Iacono J, Langerman S. Grid vertex-unfolding orthostacks Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 3742: 76-82. DOI: 10.1007/11589440_8  0.41
2005 Demaine ED, Hajiaghayi M. Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 682-689.  0.379
2004 Cabello S, Demaine ED, Rote G. Planar Embeddings of Graphs with Specified Edge Lengths Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2912: 283-294. DOI: 10.7155/Jgaa.00145  0.478
2004 Demaine ED, Fomin FV, Hajiaghayi M, Thilikos DM. Bidimensional parameters and local treewidth Siam Journal On Discrete Mathematics. 18: 501-511. DOI: 10.1137/S0895480103433410  0.44
2004 Demaine ED, Hajiaghayi M, Thilikos DM. The bidimensional theory of bounded-genus graphs Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 3153: 191-203. DOI: 10.1137/040616929  0.757
2004 Biedl T, Brejová B, Demaine ED, Hamel AM, López-Ortiz A, Vinař T. Finding hidden independent sets in interval graphs Theoretical Computer Science. 310: 287-307. DOI: 10.1016/S0304-3975(03)00422-5  0.428
2004 Demaine ED, Fleischer R, Fraenkel AS, Nowakowski RJ. Appendix B: open problems at the 2002 Dagstuhl seminar on algorithmic combinatorial game theory Theoretical Computer Science. 313: 539-543. DOI: 10.1016/J.Tcs.2003.09.012  0.357
2004 Demaine ED, Demaine ML, Fleischer R. Solitaire Clobber Theoretical Computer Science. 313: 325-338. DOI: 10.1016/J.Tcs.2003.02.001  0.327
2004 Demaine ED, Hajiaghayi M, Nishimura N, Ragde P, Thilikos DM. Approximation algorithms for classes of graphs excluding single-crossing graphs as minors Journal of Computer and System Sciences. 69: 166-195. DOI: 10.1016/J.Jcss.2003.12.001  0.503
2004 Demaine ED, Hajiaghayi MT. Diameter and treewidth in minor-closed graph families, revisited Algorithmica (New York). 40: 211-215. DOI: 10.1007/S00453-004-1106-1  0.443
2004 Demaine ED, Hajiaghayi MT. Fast algorithms for hard graph problems: Bidimensionality, minors, and local treewidth Lecture Notes in Computer Science. 3383: 517-533.  0.363
2004 Demaine ED, Hajiaghayi M. Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 15: 833-842.  0.371
2004 Demaine ED, Fomin FV, Hajiaghayi M, Thilikos DM. Subexponential parameterized algorithms on graphs of bounded-genus and H-minor-free graphs Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 15: 823-832.  0.398
2003 Bar-Joseph Z, Demaine ED, Gifford DK, Srebro N, Hamel AM, Jaakkola TS. K-ary clustering with optimal leaf ordering for gene expression data. Bioinformatics (Oxford, England). 19: 1070-8. PMID 12801867 DOI: 10.1093/Bioinformatics/Btg030  0.322
2003 Demaine ED, Hohenberger S, Liben-Nowell D. Tetris is hard, even to approximate Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2697: 351-363. DOI: 10.1142/S0218195904001354  0.359
2003 Bender CM, Bender MA, Demaine ED, Fekete SP. What is the optimal shape of a city? Journal of Physics a: Mathematical and General. 37: 147-159. DOI: 10.1088/0305-4470/37/1/010  0.338
2003 Bern M, Demaine ED, Eppstein D, Kuo E, Mantler A, Snoeyink J. Ununfoldable polyhedra with convex faces Computational Geometry: Theory and Applications. 24: 51-62. DOI: 10.1016/S0925-7721(02)00091-3  0.3
2003 Biedl T, Buss JF, Demaine ED, Demaine ML, Hajiaghayi M, Vinař T. Palindrome recognition using a multidimensional tape Theoretical Computer Science. 302: 475-480. DOI: 10.1016/S0304-3975(03)00086-0  0.677
2003 Connelly R, Demaine ED, Rote G. Straightening Polygonal Arcs and Convexifying Polygonal Cycles Discrete and Computational Geometry. 30: 205-239. DOI: 10.1007/S00454-003-0006-7  0.319
2003 Demaine ED, Langerman S, O'Rourke J. Geometric restrictions on producible polygonal protein chains Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2906: 395-404. DOI: 10.1007/S00453-005-1205-7  0.339
2002 Bose P, Brodnik A, Carlsson S, Demaine ED, Fleischer R, López-Ortiz A, Morin P, Munro JI. Online Routing In Convex Subdivisions International Journal of Computational Geometry and Applications. 12: 283-295. DOI: 10.1142/S021819590200089X  0.605
2002 Biedl T, Demaine E, Demaine M, Lazard S, Lubiw A, O'Rourke J, Robbins S, Streinu I, Toussaint G, Whitesides S. A note on reconfiguring tree linkages: Trees can lock Discrete Applied Mathematics. 117: 293-297. DOI: 10.1016/S0166-218X(01)00229-3  0.632
2002 Demaine ED, Demaine ML, Lubiw A, O'Rourke J. Enumerating foldings and unfoldings between polygons and polytopes Graphs and Combinatorics. 18: 93-104. DOI: 10.1007/S003730200005  0.631
2002 Demaine ED, Hajiaghayi MT, Thilikos DM. 1.5-approximation for treewidth of graphs excluding a graph with one crossing as a minor Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2462: 67-80. DOI: 10.1007/3-540-45753-4_8  0.48
2002 Demaine ED, Hajiaghayi MT, Thilikos DM. Exponential speedup of fixed-parameter algorithms on K33-minor-free or K5-minor-free graphs Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2518: 262-273. DOI: 10.1007/3-540-36136-7_24  0.379
2001 Aichholzer O, Demaine ED, Erickson J, Hurtado F, Overmars M, Soss M, Toussaint GT. Reconfiguring convex polygons Computational Geometry: Theory and Applications. 20: 85-95. DOI: 10.1016/S0925-7721(01)00037-2  0.304
2001 Demaine ED, López-Ortiz A, Munro JI. On universally easy classes for NP-complete problems Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 910-911. DOI: 10.1016/S0304-3975(03)00286-X  0.5
2001 Biedl T, Demaine ED, Duncan CA, Fleischer R, Kobourov SG. Tight bounds on maximal and maximum matchings Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2223: 308-319. DOI: 10.1016/J.Disc.2004.05.003  0.345
2001 Biedl T, Demaine E, Demaine M, Lazard S, Lubiw A, O'rourke J, Overmars M, Robbins S, Streinu I, Toussaint G, Whitesides S. Locked and Unlocked Polygonal Chains in Three Dimensions Discrete and Computational Geometry. 26: 269-281. DOI: 10.1007/S00454-001-0038-7  0.642
2001 Biedl TC, Bose P, Demaine ED, Lubiw A. Efficient Algorithms for Petersen's Matching Theorem Journal of Algorithms. 38: 110-134. DOI: 10.1006/jagm.2000.1132  0.682
2001 Biedl T, Demaine E, Demaine M, Lazard S, Lubiw A, O'Rourke J, Overmars M, Robbins S, Streinu I, Toussaint G, Whitesides S. Locked and unlocked polygonal chains in three dimensions Discrete and Computational Geometry. 26: 269-281.  0.53
2000 Demaine ED, Demaine ML, Mitchell JSB. Folding flat silhouettes and wrapping polyhedral packages: New results in computational origami Computational Geometry: Theory and Applications. 16: 3-21. DOI: 10.1016/S0925-7721(99)00056-5  0.411
2000 Demaine ED, Demaine ML, Lubiw A. Folding and cutting paper Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1763: 104-118.  0.643
1999 Benoit D, Demaine ED, Munro JI, Raman V. Representing trees of higher degree Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1663: 169-180. DOI: 10.1007/S00453-004-1146-6  0.535
Show low-probability matches.