Erik D. Demaine

Orcid: 0000-0003-3803-5703

Affiliations:
  • MIT, Cambridge, US


According to our database1, Erik D. Demaine authored at least 517 papers between 1996 and 2024.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 2016, "For contributions to geometric computing, data structures and graph algorithms".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Graph Threading.
Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023
Traversability, Reconfiguration, and Reachability in the Gadget Framework.
Algorithmica, November, 2023

Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets.
Theor. Comput. Sci., August, 2023

Any platonic solid can transform to another by <i>O</i>(1) refoldings.
Comput. Geom., August, 2023

2-Colorable Perfect Matching is NP-complete in 2-Connected 3-Regular Planar Graphs.
CoRR, 2023

When Can You Tile an Integer Rectangle with Integer Squares?
CoRR, 2023

Complexity of Simple Folding of Mixed Orthogonal Crease Patterns.
CoRR, 2023

Every Author as First Author.
CoRR, 2023

Complexity of Reconfiguration in Surface Chemical Reaction Networks.
CoRR, 2023

Complexity of Solo Chess with Unlimited Moves.
CoRR, 2023

This Game Is Not Going To Analyze Itself.
CoRR, 2023

Rectangular Spiral Galaxies are still hard.
Comput. Geom., 2023

Developing a tetramonohedron with minimum cut length.
Comput. Geom., 2023

Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines.
Proceedings of the 2nd Symposium on Algorithmic Foundations of Dynamic Networks, 2023

Complexity of Reconfiguration in Surface Chemical Reaction Networks.
Proceedings of the 29th International Conference on DNA Computing and Molecular Programming, 2023

2022
Area-Optimal Simple Polygonalizations: The CG Challenge 2019.
ACM J. Exp. Algorithmics, 2022

Celeste is PSPACE-hard.
CoRR, 2022

Reconfiguration of Non-crossing Spanning Trees.
CoRR, 2022

The Legend of Zelda: The Complexity of Mechanics.
CoRR, 2022

Orthogonal Fold & Cut.
CoRR, 2022

Unfolding Orthotubes with a Dual Hamiltonian Path.
CoRR, 2022

Ununfoldable polyhedra with 6 vertices or 6 faces.
Comput. Geom., 2022

Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares.
Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory, 2022

PSPACE-Completeness of Reversible Deterministic Systems.
Proceedings of the Machines, Computations, and Universality - 9th International Conference, 2022

Lower Bounds on Retroactive Data Structures.
Proceedings of the 33rd International Symposium on Algorithms and Computation, 2022

Rolling Polyhedra on Tessellations.
Proceedings of the 11th International Conference on Fun with Algorithms, 2022

Pushing Blocks via Checkable Gadgets: PSPACE-Completeness of Push-1F and Block/Box Dude.
Proceedings of the 11th International Conference on Fun with Algorithms, 2022

Hardness of Token Swapping on Trees.
Proceedings of the 30th Annual European Symposium on Algorithms, 2022

Flat Folding an Unassigned Single-Vertex Complex (Combinatorially Embedded Planar Graph with Specified Edge Lengths) Without Flat Angles.
Proceedings of the 38th International Symposium on Computational Geometry, 2022

ZHED is NP-complete.
Proceedings of the 34th Canadian Conference on Computational Geometry, 2022

Computational Complexity of Flattening Fixed-Angle Orthogonal Chains.
Proceedings of the 34th Canadian Conference on Computational Geometry, 2022

Discretization to Prove the Nonexistence of "Small" Common Unfoldings Between Polyhedra.
Proceedings of the 34th Canadian Conference on Computational Geometry, 2022

2021
On the effects of hierarchical self-assembly for reducing program-size complexity.
Theor. Comput. Sci., 2021

Belga B-Trees.
Theory Comput. Syst., 2021

Strings-and-Coins and Nimstring are PSPACE-complete.
CoRR, 2021

Folding polyominoes with holes into a cube.
Comput. Geom., 2021

Continuous flattening of all polyhedral manifolds using countably infinite creases.
Comput. Geom., 2021

Snipperclips: Cutting tools into desired polygons using themselves.
Comput. Geom., 2021

Approximating the Canadian Traveller Problem with Online Randomization.
Algorithmica, 2021

Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers.
Algorithmica, 2021

An Efficient Reversible Algorithm for Linear Regression.
Proceedings of the 2021 International Conference on Rebooting Computing (ICRC), Los Alamitos, CA, USA, November 30, 2021

Multidimensional Scaling: Approximation and Complexity.
Proceedings of the 38th International Conference on Machine Learning, 2021

1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete.
Proceedings of the 10th International Conference on Fun with Algorithms, 2021

Walking Through Doors Is Hard, Even Without Staircases: Proving PSPACE-Hardness via Planar Assemblies of Door Gadgets.
Proceedings of the 10th International Conference on Fun with Algorithms, 2021

Tatamibari Is NP-Complete.
Proceedings of the 10th International Conference on Fun with Algorithms, 2021

Characterizing Universal Reconfigurability of Modular Pivoting Robots.
Proceedings of the 37th International Symposium on Computational Geometry, 2021

Yin-Yang Puzzles are NP-complete.
Proceedings of the 33rd Canadian Conference on Computational Geometry, 2021

Any Regular Polyhedron Can Transform to Another by O(1) Refoldings.
Proceedings of the 33rd Canadian Conference on Computational Geometry, 2021

Edge-Unfolding Prismatoids: Tall or Rectangular Base.
Proceedings of the 33rd Canadian Conference on Computational Geometry, 2021

Folding Points to a Point and Lines to a Line.
Proceedings of the 33rd Canadian Conference on Computational Geometry, 2021

Scalable Equilibrium Computation in Multi-agent Influence Games on Networks.
Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021

2020
Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect.
Theor. Comput. Sci., 2020

Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible.
Theor. Comput. Sci., 2020

Rigid foldability is NP-hard.
J. Comput. Geom., 2020

Flat Folding a Strip with Parallel or Nonacute Zigzag Creases with Mountain-Valley Assignment.
J. Inf. Process., 2020

Adventures in Maze Folding Art.
J. Inf. Process., 2020

Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players.
J. Inf. Process., 2020

Tetris is NP-hard even with <i>O</i>(1) Rows or Columns.
J. Inf. Process., 2020

PSPACE-completeness of Pulling Blocks to Reach a Goal.
J. Inf. Process., 2020

Cookie Clicker.
Graphs Comb., 2020

Path Puzzles: Discrete Tomography with a Path Constraint is Hard.
Graphs Comb., 2020

Polyhedral Characterization of Reversible Hinged Dissections.
Graphs Comb., 2020

Infinite All-Layers Simple Foldability.
Graphs Comb., 2020

Tetris is NP-hard even with $O(1)$ rows or columns.
CoRR, 2020

Escaping a Polygon.
CoRR, 2020

Computing Convex Partitions for Point Sets in the Plane: The CG: SHOP Challenge 2020.
CoRR, 2020

Symmetric assembly puzzles are hard, beyond a few pieces.
Comput. Geom., 2020

Universal hinge patterns for folding strips efficiently into any grid polyhedron.
Comput. Geom., 2020

Existence and Hardness of Conveyor Belts.
Electron. J. Comb., 2020

Recursed Is Not Recursive: A Jarring Result.
Proceedings of the 31st International Symposium on Algorithms and Computation, 2020

Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess Is Hard.
Proceedings of the 31st International Symposium on Algorithms and Computation, 2020

Arithmetic Expression Construction.
Proceedings of the 31st International Symposium on Algorithms and Computation, 2020

Toward a General Complexity Theory of Motion Planning: Characterizing Which Gadgets Make Games Hard.
Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Finding Closed Quasigeodesics on Convex Polyhedra.
Proceedings of the 36th International Symposium on Computational Geometry, 2020

Some Polycubes Have No Edge Zipper Unfolding.
Proceedings of the 32nd Canadian Conference on Computational Geometry, 2020

Acutely Triangulated, Stacked, and Very Ununfoldable Polyhedra.
Proceedings of the 32nd Canadian Conference on Computational Geometry, 2020

Tribute to Godfried Toussaint.
Proceedings of the 32nd Canadian Conference on Computational Geometry, 2020

Folding Small Polyominoes into a Unit Cube.
Proceedings of the 32nd Canadian Conference on Computational Geometry, 2020

New Results in Sona Drawing: Hardness and TSP Separation.
Proceedings of the 32nd Canadian Conference on Computational Geometry, 2020

2048 Without Merging.
Proceedings of the 32nd Canadian Conference on Computational Geometry, 2020

2019
Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch.
SIAM J. Comput., 2019

Particle computation: complexity, algorithms, and logic.
Nat. Comput., 2019

Sequentially Swapping Colored Tokens on Graphs.
J. Graph Algorithms Appl., 2019

Structural sparsity of complex networks: Bounded expansion in random models and real-world graphs.
J. Comput. Syst. Sci., 2019

Some Polycubes Have No Edge-Unzipping.
CoRR, 2019

Waiting is not easy but worth it: the online TSP on the line revisited.
CoRR, 2019

Reconfiguring Undirected Paths.
Proceedings of the Algorithms and Data Structures - 16th International Symposium, 2019

Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class.
Proceedings of the 27th Annual European Symposium on Algorithms, 2019

Simulation of Programmable Matter Systems Using Active Tile-Based Self-Assembly.
Proceedings of the DNA Computing and Molecular Programming - 25th International Conference, 2019

2018
An End-to-End Approach to Self-Folding Origami Structures.
IEEE Trans. Robotics, 2018

A simple proof that the (<i>n</i><sup>2</sup> - 1)-puzzle is hard.
Theor. Comput. Sci., 2018

The fewest clues problem.
Theor. Comput. Sci., 2018

Editorial fun.
Theor. Comput. Sci., 2018

Conflict-Free Coloring of Graphs.
SIAM J. Discret. Math., 2018

Flat foldings of plane graphs with prescribed angles and edge lengths.
J. Comput. Geom., 2018

Folding Polyominoes into (Poly)Cubes.
Int. J. Comput. Geom. Appl., 2018

A General Theory of Motion Planning Complexity: Characterizing Which Gadgets Make Games Hard.
CoRR, 2018

Conic Crease Patterns with Reflecting Rule Lines.
CoRR, 2018

Losing at Checkers is Hard.
CoRR, 2018

Pachinko.
Comput. Geom., 2018

Bumpy pyramid folding.
Comput. Geom., 2018

Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams.
Algorithmica, 2018

Tree-Residue Vertex-Breaking: a new tool for proving hardness.
Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018

Nearly Optimal Separation Between Partially and Fully Retroactive Data Structures.
Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018

Solving the Rubik's Cube Optimally is NP-complete.
Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

Red-Blue Pebble Game: Complexity of Computing the Trade-Off between Cache Size and Memory Transfers.
Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, 2018

Packing Cube Nets into Rectangles with O(1) Holes.
Proceedings of the Discrete and Computational Geometry, Graphs, and Games, 2018

Toward Unfolding Doubly Covered n-Stars.
Proceedings of the Discrete and Computational Geometry, Graphs, and Games, 2018

Negative Instance for the Edge Patrolling Beacon Problem.
Proceedings of the Discrete and Computational Geometry, Graphs, and Games, 2018

Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

The Computational Complexity of Portal and Other 3D Video Games.
Proceedings of the 9th International Conference on Fun with Algorithms, 2018

Computational Complexity of Motion Planning of a Robot through Simple Gadgets.
Proceedings of the 9th International Conference on Fun with Algorithms, 2018

Computational Complexity of Generalized Push Fight.
Proceedings of the 9th International Conference on Fun with Algorithms, 2018

Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible.
Proceedings of the 9th International Conference on Fun with Algorithms, 2018

Know When to Fold 'Em: Self-assembly of Shapes by Folding in Oritatami.
Proceedings of the DNA Computing and Molecular Programming - 24th International Conference, 2018

2017
New geometric algorithms for fully connected staged self-assembly.
Theor. Comput. Sci., 2017

Folded Structures Satisfying Multiple Conditions.
J. Inf. Process., 2017

Total Tetris: Tetris with Monominoes, Dominoes, Trominoes, Pentominoes, ...
J. Inf. Process., 2017

Even 1 × <i>n</i> Edge-Matching and Jigsaw Puzzles are Really Hard.
J. Inf. Process., 2017

Folding and Punching Paper.
J. Inf. Process., 2017

Simple Folding is Really Hard.
J. Inf. Process., 2017

Unfolding and Dissection of Multiple Cubes, Tetrahedra, and Doubly Covered Squares.
J. Inf. Process., 2017

Arboral satisfaction: Recognition and LP approximation.
Inf. Process. Lett., 2017

Unfolding Genus-2 Orthogonal Polyhedra with Linear Refinement.
Graphs Comb., 2017

Embedding Stacked Polytopes on a Polynomial-Size Grid.
Discret. Comput. Geom., 2017

A simple proof that the $(n^2-1)$-puzzle is hard.
CoRR, 2017

Hamiltonicity is Hard in Thin or Polygonal Grid Graphs, but Easy in Thin Polygonal Grid Graphs.
CoRR, 2017

Minimal forcing sets for 1D origami.
CoRR, 2017

Even 1×n Edge-Matching and Jigsaw Puzzles are Really Hard.
CoRR, 2017

Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs.
Proceedings of the Algorithms and Data Structures - 15th International Symposium, 2017

Universal Shape Replicators via Self-Assembly with Attractive and Repulsive Forces.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Three Colors Suffice: Conflict-Free Coloring of Planar Graphs.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Upward Partitioned Book Embeddings.
Proceedings of the Graph Drawing and Network Visualization - 25th International Symposium, 2017

Origamizer: A Practical Algorithm for Folding Any Polyhedron.
Proceedings of the 33rd International Symposium on Computational Geometry, 2017

Push-Pull Block Puzzles are Hard.
Proceedings of the Algorithms and Complexity - 10th International Conference, 2017

Snipperclips: Cutting Tools into Desired Polygons using Themselves.
Proceedings of the 29th Canadian Conference on Computational Geometry, 2017

Common Development of Prisms, Anti-Prisms, Tetrahedra, and Wedges.
Proceedings of the 29th Canadian Conference on Computational Geometry, 2017

Computing 3SAT on a Fold-and-Cut Machine.
Proceedings of the 29th Canadian Conference on Computational Geometry, 2017

2016
Approximation Schemes for Planar Graph Problems.
Encyclopedia of Algorithms, 2016

Bidimensionality.
Encyclopedia of Algorithms, 2016

Network Creation Games.
Encyclopedia of Algorithms, 2016

Rigid origami vertices: conditions and forcing sets.
J. Comput. Geom., 2016

Folding a paper strip to minimize thickness.
J. Discrete Algorithms, 2016

Computational Complexity of Arranging Music.
CoRR, 2016

Folding Flat Crease Patterns with Thick Materials.
CoRR, 2016

Single-Player and Two-Player Buttons & Scissors Games.
CoRR, 2016

The Two-Handed Tile Assembly Model is not Intrinsically Universal.
Algorithmica, 2016

A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Cache-Adaptive Analysis.
Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, 2016

Toward an Energy Efficient Language and Compiler for (Partially) Reversible Algorithms.
Proceedings of the Reversible Computation - 8th International Conference, 2016

Energy-Efficient Algorithms.
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

The Complexity of Hex and the Jordan Curve Theorem.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Super Mario Bros. is Harder/Easier Than We Thought.
Proceedings of the 8th International Conference on Fun with Algorithms, 2016

Who Needs Crossings? Hardness of Plane Graph Rigidity.
Proceedings of the 32nd International Symposium on Computational Geometry, 2016

2015
Swapping labeled tokens on graphs.
Theor. Comput. Sci., 2015

Linear-time algorithm for sliding tokens on trees.
Theor. Comput. Sci., 2015

Fun with fonts: Algorithmic typography.
Theor. Comput. Sci., 2015

Classic Nintendo games are (computationally) hard.
Theor. Comput. Sci., 2015

You Should Be Scared of German Ghost.
J. Inf. Process., 2015

Zig-Zag Numberlink is NP-Complete.
J. Inf. Process., 2015

Characterization of Curved Creases and Rulings: Design and Analysis of Lens Tessellations.
CoRR, 2015

Worst-Case Optimal Tree Layout in External Memory.
Algorithmica, 2015

Polylogarithmic Fully Retroactive Priority Queues via Hierarchical Checkpointing.
Proceedings of the Algorithms and Data Structures - 14th International Symposium, 2015

Cache-Oblivious Iterated Predecessor Queries via Range Coalescing.
Proceedings of the Algorithms and Data Structures - 14th International Symposium, 2015

Bust-a-Move/Puzzle Bobble Is NP-complete.
Proceedings of the Discrete and Computational Geometry and Graphs - 18th Japan Conference, 2015

Continuous Flattening of Orthogonal Polyhedra.
Proceedings of the Discrete and Computational Geometry and Graphs - 18th Japan Conference, 2015

Single-Player and Two-Player Buttons & Scissors Games - (Extended Abstract).
Proceedings of the Discrete and Computational Geometry and Graphs - 18th Japan Conference, 2015

Mario Kart Is Hard.
Proceedings of the Discrete and Computational Geometry and Graphs - 18th Japan Conference, 2015

Dissection with the Fewest Pieces is Hard, Even to Approximate.
Proceedings of the Discrete and Computational Geometry and Graphs - 18th Japan Conference, 2015

Box Pleating is Hard.
Proceedings of the Discrete and Computational Geometry and Graphs - 18th Japan Conference, 2015

Particle computation: Device fan-out and binary memory.
Proceedings of the IEEE International Conference on Robotics and Automation, 2015

A Dissimilarity Measure for Comparing Origami Crease Patterns.
Proceedings of the ICPRAM 2015, 2015

Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals.
Proceedings of the 31st International Symposium on Computational Geometry, 2015

Computational complexity of numberless Shakashaka.
Proceedings of the 27th Canadian Conference on Computational Geometry, 2015

2014
UNO is hard, even for a single player.
Theor. Comput. Sci., 2014

Minimizing Movement: Fixed-Parameter Tractability.
ACM Trans. Algorithms, 2014

Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs.
ACM Trans. Algorithms, 2014

Correction: Basic Network Creation Games.
SIAM J. Discret. Math., 2014

Picture-Hanging Puzzles.
Theory Comput. Syst., 2014

Covering Folded Shapes.
J. Comput. Geom., 2014

Approximability of the subset sum reconfiguration problem.
J. Comb. Optim., 2014

Computational Complexity and an Integer Programming Model of Shakashaka.
IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2014

Computational Complexity of Piano-Hinged Dissections.
IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2014

Unfolding Orthogonal Polyhedra with Quadratic Refinement: The Delta-Unfolding Algorithm.
Graphs Comb., 2014

Structural Sparsity of Complex Networks: Random Graph Models and Linear Algorithms.
CoRR, 2014

Fast Dynamic Pointer Following via Link-Cut Trees.
CoRR, 2014

Filling a Hole in a Crease Pattern: Isometric Mapping from Prescribed Boundary Folding.
CoRR, 2014

Reprint of: Refold rigidity of convex polyhedra.
Comput. Geom., 2014

On Cartesian Trees and Range Minimum Queries.
Algorithmica, 2014

Necklaces, Convolutions, and X+Y.
Algorithmica, 2014

Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs.
Algorithmica, 2014

How to influence people with partial incentives.
Proceedings of the 23rd International World Wide Web Conference, 2014

On Streaming and Communication Complexity of the Set Cover Problem.
Proceedings of the Distributed Computing - 28th International Symposium, 2014

Polynomial-Time Algorithm for Sliding Tokens on Trees.
Proceedings of the Algorithms and Computation - 25th International Symposium, 2014

Particle computation: Designing worlds to control robot swarms with only global signals.
Proceedings of the 2014 IEEE International Conference on Robotics and Automation, 2014

An end-to-end approach to making self-folded 3D surface shapes by uniform heating.
Proceedings of the 2014 IEEE International Conference on Robotics and Automation, 2014

Canadians Should Travel Randomly.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

One Tile to Rule Them All: Simulating Any Tile Assembly System with a Single Universal Tile.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Playing Dominoes Is Hard, Except by Yourself.
Proceedings of the Fun with Algorithms - 7th International Conference, 2014

Continuously Flattening Polyhedra Using Straight Skeletons.
Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

2013
Basic Network Creation Games.
SIAM J. Discret. Math., 2013

Scheduling to minimize gaps and power consumption.
J. Sched., 2013

One-dimensional staged self-assembly.
Nat. Comput., 2013

Finding a Hamiltonian Path in a Cube with Specified Turns is Hard.
J. Inf. Process., 2013

The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs.
J. Comb. Optim., 2013

Coverage with k-transmitters in the presence of obstacles.
J. Comb. Optim., 2013

Constructing Points through Folding and Intersection.
Int. J. Comput. Geom. Appl., 2013

Folding Equilateral Plane graphs.
Int. J. Comput. Geom. Appl., 2013

A Few Lessons I've Learned.
Bull. EATCS, 2013

Bidimensional Structures: Algorithms, Combinatorics and Logic (Dagstuhl Seminar 13121).
Dagstuhl Reports, 2013

Unfolding Orthogrids with Constant Refinement.
CoRR, 2013

Refold rigidity of convex polyhedra.
Comput. Geom., 2013

Bounded-degree polyhedronization of point sets.
Comput. Geom., 2013

Non-crossing matchings of points with geometric objects.
Comput. Geom., 2013

Efficient reconfiguration of lattice-based modular robots.
Comput. Geom., 2013

Blame Trees.
Proceedings of the Algorithms and Data Structures - 13th International Symposium, 2013

Two Hands Are Better Than One (up to constant factors): Self-Assembly In The 2HAM vs. aTAM.
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Algorithms for Designing Pop-Up Cards.
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Learning Disjunctions: Near-Optimal Trade-off between Mistakes and "I Don't Know's".
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

On Wrapping Spheres and Cubes with Rectangular Paper.
Proceedings of the Discrete and Computational Geometry and Graphs, 2013

Combining Binary Search Trees.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Zipper Unfoldability of Domes and Prismoids.
Proceedings of the 25th Canadian Conference on Computational Geometry, 2013

Variations on Instant Insanity.
Proceedings of the Space-Efficient Data Structures, 2013

Reconfiguring Massive Particle Swarms with Limited, Global Control.
Proceedings of the Algorithms for Sensor Systems, 2013

2012
The price of anarchy in network creation games.
ACM Trans. Algorithms, 2012

NP-completeness of generalized Kaboozle.
J. Inf. Process., 2012

Constant Price of Anarchy in Network-Creation Games via Public-Service Advertising.
Internet Math., 2012

Ghost chimneys.
Int. J. Comput. Geom. Appl., 2012

Hinged Dissections Exist.
Discret. Comput. Geom., 2012

Reconfiguration of list edge-colorings in a graph.
Discret. Appl. Math., 2012

One Tile to Rule Them All: Simulating Any Turing Machine, Tile Assembly System, or Tiling System with a Single Puzzle Piece
CoRR, 2012

Classic Nintendo Games are (NP-)Hard
CoRR, 2012

Two Hands Are Better Than One (up to constant factors)
CoRR, 2012

On k-convex polygons.
Comput. Geom., 2012

Any Monotone Function Is Realized by Interlocked Polygons.
Algorithms, 2012

Origami Robots and Star Trek Replicators.
Proceedings of the Algorithms and Computation - 23rd International Symposium, 2012

2011
Programmable Assembly With Universally Foldable Strings (Moteins).
IEEE Trans. Robotics, 2011

On the complexity of reconfiguration problems.
Theor. Comput. Sci., 2011

Planning to fold multiple objects from a single self-folding sheet.
Robotica, 2011

Efficient constant-velocity reconfiguration of crystalline robots.
Robotica, 2011

The Voronoi game on graphs and its complexity.
J. Graph Algorithms Appl., 2011

Computing Signed Permutations of Polygons.
Int. J. Comput. Geom. Appl., 2011

(Non)Existence of Pleated Folds: How Paper Folds Between Creases.
Graphs Comb., 2011

Continuous Blooming of Convex Polyhedra.
Graphs Comb., 2011

Algorithmic Folding Complexity.
Graphs Comb., 2011

Integer point sets minimizing average pairwise L<sub>1</sub> distance: What is the optimal shape of a town?
Comput. Geom., 2011

Covering points by disjoint boxes with outliers.
Comput. Geom., 2011

The Stackelberg Minimum Spanning Tree Game.
Algorithmica, 2011

Flattening Fixed-Angle Chains Is Strongly NP-Hard.
Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

Lossless Fault-Tolerant Data Structures with Additive Overhead.
Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

Contraction decomposition in h-minor-free graphs and algorithmic applications.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor (extended abstract).
Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

Constructing Strings at the Nano Scale via Staged Self-assembly.
Proceedings of the String Processing and Information Retrieval, 2011

A Generalization of the Source Unfolding of Convex Polyhedra.
Proceedings of the Computational Geometry - XIV Spanish Meeting on Computational Geometry, 2011

Meshes Preserving Minimum Feature Size.
Proceedings of the Computational Geometry - XIV Spanish Meeting on Computational Geometry, 2011

Algorithms for Solving Rubik's Cubes.
Proceedings of the Algorithms - ESA 2011, 2011

Remarks on Separating Words.
Proceedings of the Descriptional Complexity of Formal Systems, 2011

Edge-guarding Orthogonal Polyhedra.
Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011

Expansive Motions for d-Dimensional Open Chains.
Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011

Convexifying Polygons Without Losing Visibilities.
Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011

Common Developments of Several Different Orthogonal Boxes.
Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011

A Topologically Convex Vertex-Ununfoldable Polyhedron.
Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011

Edge-Unfolding Orthogonal Polyhedra is Strongly NP-Complete.
Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011

O(1)-Approximations for Maximum Movement Problems.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010
Deploying sensor networks with guaranteed fault tolerance.
IEEE/ACM Trans. Netw., 2010

Filling Holes in Triangular Meshes Using Digital Images by Curve Unfolding.
Int. J. Shape Model., 2010

Grid Vertex-Unfolding Orthostacks.
Int. J. Comput. Geom. Appl., 2010

Generalized D-Forms Have No Spurious Creases.
Discret. Comput. Geom., 2010

Locked and Unlocked Chains of Planar Shapes.
Discret. Comput. Geom., 2010

Integer Point Sets Minimizing Average Pairwise L1-Distance: What is the Optimal Shape of a Town?
CoRR, 2010

Circle Packing for Origami Design Is Hard
CoRR, 2010

Self-Assembly of Arbitrary Shapes with RNA and DNA tiles (extended abstract)
CoRR, 2010

The complexity of UNO
CoRR, 2010

Approximation algorithms via contraction decomposition.
Comb., 2010

Confluently Persistent Tries for Efficient Version Control.
Algorithmica, 2010

Algorithmic Graph Minors and Bidimensionality.
Proceedings of the Graph Theoretic Concepts in Computer Science, 2010

Minimizing the Diameter of a Network Using Shortcut Edges.
Proceedings of the Algorithm Theory, 2010

Scheduling to minimize power consumption using submodular functions.
Proceedings of the SPAA 2010: Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2010

Decomposition, Approximation, and Coloring of Odd-Minor-Free Graphs.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Cache-Oblivious Dynamic Dictionaries with Update/Query Tradeoffs.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Shape Replication through Self-Assembly and RNase Enzymes.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Reconfigurable asynchronous logic automata: (RALA).
Proceedings of the 37th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2010


UNO Is Hard, Even for a Single Player.
Proceedings of the Fun with Algorithms, 5th International Conference, 2010

Kaboozle Is NP-complete, Even in a Strip.
Proceedings of the Fun with Algorithms, 5th International Conference, 2010

10091 Abstracts Collection - Data Structures.
Proceedings of the Data Structures, 28.02. - 05.03.2010, 2010

Coverage with <i>k</i>-Transmitters in the Presence of Obstacles.
Proceedings of the Combinatorial Optimization and Applications, 2010

Making Polygons by Simple Folds and One Straight Cut.
Proceedings of the Computational Geometry, Graphs and Applications, 2010

Common Unfoldings of Polyominoes and Polycubes.
Proceedings of the Computational Geometry, Graphs and Applications, 2010

Zipper unfoldings of polyhedral complexes.
Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, 2010

Open problem session.
Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, 2010

Any monotone boolean function can be realized by interlocked polygons.
Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, 2010

2009
An optimal decomposition algorithm for tree edit distance.
ACM Trans. Algorithms, 2009

Minimizing movement.
ACM Trans. Algorithms, 2009

The price of anarchy in cooperative network creation games.
SIGecom Exch., 2009

Refolding Planar Polygons.
Discret. Comput. Geom., 2009

A Universal Crease Pattern for Folding Orthogonal Shapes
CoRR, 2009

Minimum feature size preserving decompositions
CoRR, 2009

Reconfiguration of 3D Crystalline Robots Using O(log n) Parallel Moves
CoRR, 2009

A Generalized Carpenter's Rule Theorem for Self-Touching Linkages
CoRR, 2009

The distance geometry of music.
Comput. Geom., 2009

Wrapping spheres with flat paper.
Comput. Geom., 2009

Linear reconfiguration of cube-style modular robots.
Comput. Geom., 2009

Dynamic ham-sandwich cuts in the plane.
Comput. Geom., 2009

Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction.
Algorithmica, 2009

Minimal Locked Trees.
Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

Additive approximation algorithms for list-coloring minor-closed class of graphs.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

The geometry of binary search trees.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Filling holes in triangular meshes by curve unfolding.
Proceedings of the IEEE International Conference on Shape Modeling and Applications, 2009

Folding a Better Checkerboard.
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

Algorithmic Folding Complexity.
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

A Distributed boundary detection algorithm for multi-robot systems.
Proceedings of the 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2009

Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Algorithms Meet Art, Puzzles, and Magic.
Proceedings of the Algorithms, 2009

A Pseudopolynomial Algorithm for Alexandrov's Theorem.
Proceedings of the Computational Geometry, 08.03. - 13.03.2009, 2009

09511 Open Problems - Parameterized complexity and approximation algorithms.
Proceedings of the Parameterized complexity and approximation algorithms, 13.12., 2009

09511 Executive Summary - Parameterized complexity and approximation algorithms.
Proceedings of the Parameterized complexity and approximation algorithms, 13.12., 2009

09511 Abstracts Collection - Parameterized complexity and approximation algorithms.
Proceedings of the Parameterized complexity and approximation algorithms, 13.12., 2009

Open Problems from CCCG 2008.
Proceedings of the 21st Annual Canadian Conference on Computational Geometry, 2009

Relaxed Gabriel Graphs.
Proceedings of the 21st Annual Canadian Conference on Computational Geometry, 2009

Invited Talk I Actuator Nets: Folding, Reconfiguring and Deploying Sensors.
Proceedings of the Algorithmic Aspects of Wireless Sensor Networks, 2009

Games, puzzles and computation.
A K Peters, ISBN: 978-1-56881-322-6, 2009

2008
Bidimensionality.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Approximation Schemes for Planar Graph Problems.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Ordinal embeddings of minimum relaxation: General properties, trees, and ultrametrics.
ACM Trans. Algorithms, 2008

Combination Can Be Hard: Approximability of the Unique Coverage Problem.
SIAM J. Comput., 2008

Staged self-assembly: nanomanufacture of arbitrary shapes with <i>O</i> (1) glues.
Nat. Comput., 2008

Approximability of partitioning graphs with supply and demand.
J. Discrete Algorithms, 2008

Realizing partitions respecting full and partial order information.
J. Discrete Algorithms, 2008

Cauchy's Arm Lemma on a Growing Sphere
CoRR, 2008

Staged Self-Assembly:Nanomanufacture of Arbitrary Shapes with O(1) Glues
CoRR, 2008

A Locked Orthogonal Tree
CoRR, 2008

Edge-unfolding nested polyhedral bands.
Comput. Geom., 2008

Linearity of grid minors in treewidth with applications through bidimensionality.
Comb., 2008

The Bidimensionality Theory and Its Algorithmic Applications.
Comput. J., 2008

Communication-Aware Processor Allocation for Supercomputers: Finding Point Sets of Small Average Distance.
Algorithmica, 2008

Subquadratic Algorithms for 3SUM.
Algorithmica, 2008

Optimally Adaptive Integration of Univariate Lipschitz Functions.
Algorithmica, 2008

Realistic Reconfiguration of Crystalline (and Telecube) Robots.
Proceedings of the Algorithmic Foundation of Robotics VIII, 2008

Reconfiguration of Cube-Style Modular Robots Using O(logn) Parallel Moves.
Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

Moving-Baseline Localization.
Proceedings of the 7th International Conference on Information Processing in Sensor Networks, 2008

Constraint Logic: A Uniform Framework for Modeling Computation as Games.
Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

Computational Balloon Twisting: The Theory of Balloon Polyhedra.
Proceedings of the 20th Annual Canadian Conference on Computational Geometry, 2008

Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction.
Proceedings of the Approximation, 2008

2007
A unified access bound on comparison-based dynamic dictionaries.
Theor. Comput. Sci., 2007

Retroactive data structures.
ACM Trans. Algorithms, 2007

Dynamic Optimality - Almost.
SIAM J. Comput., 2007

An Optimal Cache-Oblivious Priority Queue and Its Application to Graph Algorithms.
SIAM J. Comput., 2007

Planar Embeddings of Graphs with Specified Edge Lengths.
J. Graph Algorithms Appl., 2007

Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity.
Graphs Comb., 2007

Quickly deciding minor-closed parameters in general graphs.
Eur. J. Comb., 2007

Geodesic Ham-Sandwich Cuts.
Discret. Comput. Geom., 2007

Plane Embeddings of Planar Graph Metrics.
Discret. Comput. Geom., 2007

A Pseudopolynomial Time <i>O</i> (log <i>n</i> )-Approximation Algorithm for Art Gallery Problems.
Proceedings of the Algorithms and Data Structures, 10th International Workshop, 2007

Deflating the Pentagon.
Proceedings of the Computational Geometry and Graph Theory, 2007

07281 Open Problems -- Structure Theory and FPT Algorithmcs for Graphs, Digraphs and Hypergraphs.
Proceedings of the Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs, 08.07., 2007

07281 Abstracts Collection -- Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs.
Proceedings of the Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs, 08.07., 2007

Tight bounds for dynamic convex hull queries (again).
Proceedings of the 23rd ACM Symposium on Computational Geometry, 2007

Open Problems from CCCG 2006.
Proceedings of the 19th Annual Canadian Conference on Computational Geometry, 2007

On Rolling Cube Puzzles.
Proceedings of the 19th Annual Canadian Conference on Computational Geometry, 2007

Disjoint Segments Have Convex Partitions with 2-Edge Connected Dual Graphs.
Proceedings of the 19th Annual Canadian Conference on Computational Geometry, 2007

Vertex Pops and Popturns.
Proceedings of the 19th Annual Canadian Conference on Computational Geometry, 2007

Geometric folding algorithms - linkages, origami, polyhedra.
Cambridge University Press, 2007

2006
Online searching with turn cost.
Theor. Comput. Sci., 2006

Correlation clustering in general weighted graphs.
Theor. Comput. Sci., 2006

The Bidimensional Theory of Bounded-Genus Graphs.
SIAM J. Discret. Math., 2006

Logarithmic Lower Bounds in the Cell-Probe Model.
SIAM J. Comput., 2006

Morpion Solitaire.
Theory Comput. Syst., 2006

Puzzles, Art, and Magic with Algorithms.
Theory Comput. Syst., 2006

Low-Dimensional Embedding with Extra Information.
Discret. Comput. Geom., 2006

An O(n^3)-Time Algorithm for Tree Edit Distance
CoRR, 2006

EpiChord: Parallelizing the Chord lookup algorithm with reactive routing state management.
Comput. Commun., 2006

Geometric Restrictions on Producible Polygonal Protein Chains.
Algorithmica, 2006

Lower bounds for asymmetric communication channels and distributed source coding.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

De Dictionariis Dynamicis Pauco Spatio Utentibus (<i>lat.</i> On Dynamic Dictionaries Using Little Space).
Proceedings of the LATIN 2006: Theoretical Informatics, 2006

Origami, Linkages, and Polyhedra: Folding with Algorithms.
Proceedings of the Algorithms, 2006

Necklaces, Convolutions, and <i>X</i> + <i>Y</i>.
Proceedings of the Algorithms, 2006

Open Problems: Open Problems from CCCG 2005.
Proceedings of the 18th Annual Canadian Conference on Computational Geometry, 2006

Polygons Flip Finitely: Flaws and a Fix.
Proceedings of the 18th Annual Canadian Conference on Computational Geometry, 2006

Paul Erdos Memorial Lecture: Linkage Folding: From Erdos to Proteins.
Proceedings of the 18th Annual Canadian Conference on Computational Geometry, 2006

Curves in the Sand: Algorithmic Drawing.
Proceedings of the 18th Annual Canadian Conference on Computational Geometry, 2006

2005
PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation.
Theor. Comput. Sci., 2005

Games on triangulations.
Theor. Comput. Sci., 2005

Fixed-parameter algorithms for (<i>k</i>, <i>r</i>)-center in planar graphs and map graphs.
ACM Trans. Algorithms, 2005

Cache-Oblivious B-Trees.
SIAM J. Comput., 2005

Optimal Covering Tours with Turn Costs.
SIAM J. Comput., 2005

Subexponential parameterized algorithms on bounded-genus graphs and <i>H</i>-minor-free graphs.
J. ACM, 2005

Separating Point Sets in Polygonal Environments.
Int. J. Comput. Geom. Appl., 2005

Optimal Adaptive Algorithms for Finding the nearest and Farthest Point on a Parametric Black-box Curve.
Int. J. Comput. Geom. Appl., 2005

Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries.
Discret. Comput. Geom., 2005

De Dictionariis Dynamicis Pauco Spatio Utentibus
CoRR, 2005

Bidimensionality, Map Graphs, and Grid Minors
CoRR, 2005

Hinged dissection of polyominoes and polyforms.
Comput. Geom., 2005

Exponential Speedup of Fixed-Parameter Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors.
Algorithmica, 2005

Representing Trees of Higher Degree.
Algorithmica, 2005

Fast allocation and deallocation with an improved buddy system.
Acta Informatica, 2005

Hinged Dissection of Polypolyhedra.
Proceedings of the Algorithms and Data Structures, 9th International Workshop, 2005

Communication-Aware Processor Allocation for Supercomputers.
Proceedings of the Algorithms and Data Structures, 9th International Workshop, 2005

Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Bidimensionality: new connections between FPT algorithms and PTASs.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Deploying sensor networks with guaranteed capacity and fault tolerance.
Proceedings of the 6th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, 2005

Mobile-assisted localization in wireless sensor networks.
Proceedings of the INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies, 2005

Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Optimizing a 2D Function Satisfying Unimodality Properties.
Proceedings of the Algorithms, 2005

The Distance Geometry of Deep Rhythms and Scales.
Proceedings of the 17th Canadian Conference on Computational Geometry, 2005

Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane.
Proceedings of the 17th Canadian Conference on Computational Geometry, 2005

2004
Geometry and Topology of Polygonal Linkages.
Proceedings of the Handbook of Discrete and Computational Geometry, Second Edition., 2004

Appendix B: Open problems at the 2002 Dagstuhl Seminar on Algorithmic Combinatorial Game Theory.
Theor. Comput. Sci., 2004

Solitaire Clobber.
Theor. Comput. Sci., 2004

Finding hidden independent sets in interval graphs.
Theor. Comput. Sci., 2004

Bidimensional Parameters and Local Treewidth.
SIAM J. Discret. Math., 2004

Approximation algorithms for classes of graphs excluding single-crossing graphs as minors.
J. Comput. Syst. Sci., 2004

Tetris is hard, even to approximate.
Int. J. Comput. Geom. Appl., 2004

Tight bounds on maximal and maximum matchings.
Discret. Math., 2004

Fun-Sort--or the chaos of unordered binary search.
Discret. Appl. Math., 2004

Worst-Case Optimal Tree Layout in a Memory Hierarchy
CoRR, 2004

Proximate point searching.
Comput. Geom., 2004

When can you fold a map?
Comput. Geom., 2004

Diameter and Treewidth in Minor-Closed Graph Families, Revisited.
Algorithmica, 2004

Lower bounds for dynamic connectivity.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Finding Frequent Items in Sliding Windows with Multinomially-Distributed Item Frequencies.
Proceedings of the 16th International Conference on Scientific and Statistical Database Management (SSDBM 2004), 2004

Tight bounds for the partial-sums problem.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Interpolation search for non-independent data.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Equivalence of local treewidth and linear local treewidth and its algorithmic applications.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Subexponential parameterized algorithms on graphs of bounded-genus and <i>H</i>-minor-free graphs.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

A Simplified, Dynamic Unified Structure.
Proceedings of the LATIN 2004: Theoretical Informatics, 2004

Puzzles, Art, and Magic with Algorithms.
Proceedings of the Algorithms and Computation, 15th International Symposium, 2004

Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth.
Proceedings of the Graph Drawing, 12th International Symposium, 2004

04301 Abstracts Collection - Cache-Oblivious and Cache-Aware Algorithms.
Proceedings of the Cache-Oblivious and Cache-Aware Algorithms, 18.07. - 23.07.2004, 2004

An energy-driven approach to linkage unfolding.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

Continuous foldability of polygonal paper.
Proceedings of the 16th Canadian Conference on Computational Geometry, 2004

Unfolding polyhedral bands.
Proceedings of the 16th Canadian Conference on Computational Geometry, 2004

2003
On universally easy classes for NP-complete problems.
Theor. Comput. Sci., 2003

Palindrome recognition using a multidimensional tape.
Theor. Comput. Sci., 2003

A linear lower bound on index size for text retrieval.
J. Algorithms, 2003

Straightening Polygonal Arcs and Convexifying Polygonal Cycles.
Discret. Comput. Geom., 2003

Interlocked open and closed linkages with few joints.
Comput. Geom., 2003

Pushing blocks is hard.
Comput. Geom., 2003

Ununfoldable polyhedra with convex faces.
Comput. Geom., 2003

Long proteins with unique optimal foldings in the H-P model.
Comput. Geom., 2003

K-ary Clustering with Optimal Leaf Ordering for Gene Expression Data.
Bioinform., 2003

Anchor-free distributed localization in sensor networks.
Proceedings of the 1st International Conference on Embedded Networked Sensor Systems, 2003

Correlation Clustering with Partial Information.
Proceedings of the Approximation, 2003

Identifying frequent items in sliding windows over on-line packet streams.
Proceedings of the 3rd ACM SIGCOMM Internet Measurement Conference, 2003

Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs.
Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

Optimal Dynamic Video-on-Demand Using Adaptive Broadcasting.
Proceedings of the Algorithms, 2003

Tetris is Hard, Even to Approximate.
Proceedings of the Computing and Combinatorics, 9th Annual International Conference, 2003

Hinged Dissection of Polygons is Hard.
Proceedings of the 15th Canadian Conference on Computational Geometry, 2003

On the Complexity of Halfspace Volume Queries.
Proceedings of the 15th Canadian Conference on Computational Geometry, 2003

Open Problems from ALENEX 2003.
Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments, 2003

2002
Online Routing in Convex Subdivisions.
Int. J. Comput. Geom. Appl., 2002

Enumerating Foldings and Unfoldings Between Polygons and Polytopes.
Graphs Comb., 2002

Balanced <i>k</i>-colorings.
Discret. Math., 2002

Flipturning Polygons.
Discret. Comput. Geom., 2002

A note on reconfiguring tree linkages: trees can lock.
Discret. Appl. Math., 2002

Efficient Tree Layout in a Multilevel Memory Hierarchy
CoRR, 2002

Coin-Moving Puzzles
CoRR, 2002

Open Problems from CCCG 2002
CoRR, 2002

Robot Localization without Depth Perception.
Proceedings of the Algorithm Theory, 2002

Cache-oblivious priority queue and graph algorithm applications.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Playing with Triangulations.
Proceedings of the Discrete and Computational Geometry, Japanese Conference, 2002

Exponential Speedup of Fixed-Parameter Algorithms on K<sub>3, 3</sub>-Minor-Free or K<sub>5</sub>-Minor-Free Graphs.
Proceedings of the Algorithms and Computation, 13th International Symposium, 2002

Flat-State Connectivity of Linkages under Dihedral Motions.
Proceedings of the Algorithms and Computation, 13th International Symposium, 2002

The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications.
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

Frequency Estimation of Internet Packet Streams with Limited Space.
Proceedings of the Algorithms, 2002

Efficient Tree Layout in a Multilevel Memory Hierarchy.
Proceedings of the Algorithms, 2002

Two Simplified Algorithms for Maintaining Order in a List.
Proceedings of the Algorithms, 2002

Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy.
Proceedings of the Algorithms, 2002

Interlocked open linkages with few joints.
Proceedings of the 18th Annual Symposium on Computational Geometry, 2002

Vertex-unfoldings of simplicial manifolds.
Proceedings of the 18th Annual Symposium on Computational Geometry, 2002

Open problems from cccg 2001.
Proceedings of the 14th Canadian Conference on Computational Geometry, 2002

Push-2-f is pspace-complete.
Proceedings of the 14th Canadian Conference on Computational Geometry, 2002

Tighter bounds on the genus of nonorthogonal polyhedra built from rectangles.
Proceedings of the 14th Canadian Conference on Computational Geometry, 2002

On flat-state connectivity of chains with fixed acute angles.
Proceedings of the 14th Canadian Conference on Computational Geometry, 2002

-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2002

2001
Generalized Communicators in the Message Passing Interface.
IEEE Trans. Parallel Distributed Syst., 2001

Efficient Algorithms for Petersen's Matching Theorem.
J. Algorithms, 2001

Locked and Unlocked Polygonal Chains in Three Dimensions.
Discret. Comput. Geom., 2001

Vertex-Unfoldings of Simplicial Polyhedra
CoRR, 2001

The Complexity of Clickomania
CoRR, 2001

Polygons cuttable by a circular saw.
Comput. Geom., 2001

Reconfiguring convex polygons.
Comput. Geom., 2001

Playing Games with Algorithms: Algorithmic Combinatorial Game Theory.
Proceedings of the Mathematical Foundations of Computer Science 2001, 2001

Open problems from cccg 2000.
Proceedings of the 13th Canadian Conference on Computational Geometry, 2001

Reaching folded states of a rectangular piece of paper.
Proceedings of the 13th Canadian Conference on Computational Geometry, 2001

Short interlocked linkages.
Proceedings of the 13th Canadian Conference on Computational Geometry, 2001

Pushing blocks is np-complete for noncrossing solution paths.
Proceedings of the 13th Canadian Conference on Computational Geometry, 2001

The cccg 2001 logo.
Proceedings of the 13th Canadian Conference on Computational Geometry, 2001

Experiments on Adaptive Set Intersections for Text Retrieval Systems.
Proceedings of the Algorithm Engineering and Experimentation, Third International Workshop, 2001

2000
Examples, Counterexamples, and Enumeration Results for Foldings and Unfoldings between Polygons and Polytopes
CoRR, 2000

PushPush is NP-hard in 2D
CoRR, 2000

Phutball Endgames are Hard
CoRR, 2000

Folding flat silhouettes and wrapping polyhedral packages: New results in computational origami.
Comput. Geom., 2000

Adaptive set intersections, unions, and differences.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Folding and Unfolding Linkages, Paper, and Polyhedra.
Proceedings of the Discrete and Computational Geometry, Japanese Conference, 2000

Straighting Polygonal Arcs and Convexifying Polygonal Cycles.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Every Polygon Can Be Untangled.
EuroCG, 2000

Session O1: Open Problems and Planning.
Proceedings of the 12th Canadian Conference on Computational Geometry, 2000

PushPush and Push-1 are NP-hard in 2D.
Proceedings of the 12th Canadian Conference on Computational Geometry, 2000

1999
Computational geometry column 37.
SIGACT News, 1999

Resizable Arrays in Optimal Time and Space.
Proceedings of the Algorithms and Data Structures, 6th International Workshop, 1999

Representing Trees of Higer Degree.
Proceedings of the Algorithms and Data Structures, 6th International Workshop, 1999

Folding and One Straight Cut Suffice.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Locked and Unlocked Polygonal Chains in 3D.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Convexifying Monotone Polygons.
Proceedings of the Algorithms and Computation, 10th International Symposium, 1999

Fast Allocation and Deallocation with an Improved Buddy System.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1999

Metamorphosis of the Cube.
Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

Hinged dissections of polyominoes and polyforms.
Proceedings of the 11th Canadian Conference on Computational Geometry, 1999

Ununfoldable polyhedra.
Proceedings of the 11th Canadian Conference on Computational Geometry, 1999

1998
C to Java: Converting Pointers into References.
Concurr. Pract. Exp., 1998

Folding and Cutting Paper.
Proceedings of the Discrete and Computational Geometry, Japanese Conference, 1998

Protocols for Non-Deterministic Communication over Synchronous Channels.
Proceedings of the 12th International Parallel Processing Symposium / 9th Symposium on Parallel and Distributed Processing (IPPS/SPDP '98), March 30, 1998

Planar Drawings of Origami Polyhedra.
Proceedings of the Graph Drawing, 6th International Symposium, 1998

Hiding disks in folded polygons.
Proceedings of the 10th Canadian Conference on Computational Geometry, 1998

Unfolding some classes of orthogonal polyhedra.
Proceedings of the 10th Canadian Conference on Computational Geometry, 1998

On reconfiguring tree linkages: Trees can lock.
Proceedings of the 10th Canadian Conference on Computational Geometry, 1998

1996
A Novel Routing Algorithm for k-Ary n-Cube Interconnection Networks.
Int. J. High Speed Comput., 1996


  Loading...