Erik D. Demaine

According to our database1, Erik D. Demaine
  • authored at least 537 papers between 1996 and 2017.
  • has a "Dijkstra number"2 of four.

Awards

ACM Fellow

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepage:

On csauthors.net:

Bibliography

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

Embedding Stacked Polytopes on a Polynomial-Size Grid.
Discrete & Computational Geometry, 2017

Symmetric Assembly Puzzles are Hard, Beyond a Few Pieces.
CoRR, 2017

Minimal forcing sets for 1D origami.
CoRR, 2017

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

Three Colors Suffice: Conflict-Free Coloring of Planar Graphs.
CoRR, 2017

Sequentially Swapping Colored Tokens on Graphs.
Proceedings of the WALCOM: Algorithms and Computation, 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

Push-Pull Block Puzzles are Hard.
Proceedings of the Algorithms and Complexity - 10th International Conference, 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.
JoCG, 2016

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

Toward an Energy Efficient Language and Compiler for (Partially) Reversible Algorithms.
CoRR, 2016

Computational Complexity of Arranging Music.
CoRR, 2016

Folding Flat Crease Patterns with Thick Materials.
CoRR, 2016

Energy-Efficient Algorithms.
CoRR, 2016

The Computational Complexity of Portal and Other 3D Video Games.
CoRR, 2016

Unfolding Genus-2 Orthogonal Polyhedra with Linear Refinement.
CoRR, 2016

Universal Shape Replicators via Self-Assembly with Attractive and Repulsive Forces.
CoRR, 2016

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

Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron.
CoRR, 2016

Pachinko.
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

The Fewest Clues Problem.
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.
JIP, 2015

Zig-Zag Numberlink is NP-Complete.
JIP, 2015

Bust-a-Move/Puzzle Bobble is NP-Complete.
CoRR, 2015

New Geometric Algorithms for Fully Connected Staged Self-Assembly.
CoRR, 2015

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

Dissection with the Fewest Pieces is Hard, Even to Approximate.
CoRR, 2015

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

Folding a Paper Strip to Minimize Thickness.
Proceedings of the WALCOM: Algorithms and Computation - 9th International Workshop, 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

Symmetric Assembly Puzzles are Hard, Beyond a Few Pieces.
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

New Geometric Algorithms for Fully Connected Staged Self-Assembly.
Proceedings of the DNA Computing and Molecular Programming - 21st International Conference, 2015

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

Folding Polyominoes into (Poly)Cubes.
Proceedings of the 27th Canadian Conference 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. Discrete Math., 2014

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

Covering Folded Shapes.
JoCG, 2014

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

Computational Complexity and an Integer Programming Model of Shakashaka.
IEICE Transactions, 2014

Computational Complexity of Piano-Hinged Dissections.
IEICE Transactions, 2014

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

Embedding Stacked Polytopes on a Polynomial-Size Grid.
CoRR, 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

How to Influence People with Partial Incentives.
CoRR, 2014

Folding a Paper Strip to Minimize Thickness.
CoRR, 2014

Polynomial-Time Algorithm for Sliding Tokens on Trees.
CoRR, 2014

Fun with Fonts: Algorithmic Typography.
CoRR, 2014

Particle Computation: Designing Worlds to Control Robot Swarms with only Global Signals.
CoRR, 2014

Covering Folded Shapes.
CoRR, 2014

Zig-Zag Numberlink is NP-Complete.
CoRR, 2014

Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths.
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

Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths.
Proceedings of the Graph Drawing - 22nd International Symposium, GD 2014, Würzburg, 2014

Swapping Labeled Tokens on Graphs.
Proceedings of the Fun with Algorithms - 7th International Conference, 2014

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

Fun with Fonts: Algorithmic Typography.
Proceedings of the Fun with Algorithms - 7th International Conference, 2014

Classic Nintendo Games Are (Computationally) Hard.
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

Bumpy Pyramid Folding.
Proceedings of the 26th Canadian Conference on Computational Geometry, 2014

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

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

One-dimensional staged self-assembly.
Natural Computing, 2013

Finding a Hamiltonian Path in a Cube with Specified Turns is Hard.
JIP, 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. Geometry Appl., 2013

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

A Few Lessons I've Learned.
Bulletin of the EATCS, 2013

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

Combining Binary Search Trees
CoRR, 2013

The two-handed tile assembly model is not intrinsically universal.
CoRR, 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

The Two-Handed Tile Assembly Model Is Not Intrinsically Universal.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

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

Computational complexity and an integer programming model of Shakashaka.
Proceedings of the 25th Canadian Conference on Computational Geometry, 2013

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

Covering Folded Shapes.
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.
JIP, 2012

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

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

Hinged Dissections Exist.
Discrete & Computational Geometry, 2012

Reconfiguration of list edge-colorings in a graph.
Discrete Applied Mathematics, 2012

Necklaces, Convolutions, and X+Y
CoRR, 2012

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

Minimizing Movement: Fixed-Parameter Tractability
CoRR, 2012

Picture-Hanging Puzzles
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

Picture-Hanging Puzzles.
Proceedings of the Fun with Algorithms - 6th International Conference, 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. Geometry Appl., 2011

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

Continuous Blooming of Convex Polyhedra.
Graphs and Combinatorics, 2011

Algorithmic Folding Complexity.
Graphs and Combinatorics, 2011

Unfolding Orthogonal Polyhedra with Quadratic Refinement: The Delta-Unfolding Algorithm
CoRR, 2011

Algorithms for Solving Rubik's Cubes
CoRR, 2011

Remarks on separating words
CoRR, 2011

Integer point sets minimizing average pairwise L1 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

Approximability of the Subset Sum Reconfiguration Problem.
Proceedings of the Theory and Applications of Models of Computation, 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

Embedding Stacked Polytopes on a Polynomial-Size Grid.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 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

Folding Equilateral Plane Graphs.
Proceedings of the Algorithms and Computation - 22nd International Symposium, 2011

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

One-Dimensional Staged Self-assembly.
Proceedings of the DNA Computing and Molecular Programming - 17th International Conference, 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.
International Journal of Shape Modeling, 2010

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

Generalized D-Forms Have No Spurious Creases.
Discrete & Computational Geometry, 2010

Locked and Unlocked Chains of Planar Shapes.
Discrete & Computational Geometry, 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

On k-Convex Polygons
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.
Combinatorica, 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

Constant Price of Anarchy in Network Creation Games via Public Service Advertising.
Proceedings of the Algorithms and Models for the Web-Graph - 7th International Workshop, 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

Basic network creation games.
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

Matching Points with Things.
Proceedings of the LATIN 2010: Theoretical Informatics, 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 k-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

Ghost chimneys.
Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, 2010

Bounded-degree polyhedronization of point sets.
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 Exchanges, 2009

Refolding Planar Polygons.
Discrete & Computational Geometry, 2009

Covering Points by Disjoint Boxes with Outliers
CoRR, 2009

A Universal Crease Pattern for Folding Orthogonal Shapes
CoRR, 2009

The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs
CoRR, 2009

Minimum feature size preserving decompositions
CoRR, 2009

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

(Non)existence of Pleated Folds: How Paper Folds Between Creases
CoRR, 2009

Continuous Blooming of Convex Polyhedra
CoRR, 2009

The Price of Anarchy in Cooperative Network Creation Games
CoRR, 2009

Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs
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

The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs.
Proceedings of the Internet and Network Economics, 5th International Workshop, 2009

A Pseudopolynomial Algorithm for Alexandrov's Theorem.
Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

Reconfiguration of List Edge-Colorings in a Graph.
Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

Algorithms Meet Art, Puzzles, and Magic.
Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

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

The Price of Anarchy in Cooperative Network Creation Games.
Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs.
Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 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

On Cartesian Trees and Range Minimum Queries.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

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

Minimizing Movement: Fixed-Parameter Tractability.
Proceedings of the Algorithms, 2009

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

Efficient Reconfiguration of Lattice-Based Modular Robots.
Proceedings of the 4th European Conference on Mobile Robots, 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

Integer Point Sets Minimizing Average Pairwise l1 Distance: What is the Optimal Shape of a Town?
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

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

2008
Bidimensionality.
Proceedings of the Encyclopedia of Algorithms, 2008

Approximation Schemes for Planar Graph Problems.
Proceedings of the Encyclopedia of Algorithms, 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 O (1) glues.
Natural Computing, 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

A Pseudopolynomial Algorithm for Alexandrov's Theorem
CoRR, 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.
Combinatorica, 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

Confluently Persistent Tries for Efficient Version Control.
Proceedings of the Algorithm Theory, 2008

Algorithmic Graph Minors and Bidimensionality.
Proceedings of the Parameterized and Exact Computation, Third International Workshop, 2008

On the Complexity of Reconfiguration Problems.
Proceedings of the Algorithms and Computation, 19th International Symposium, 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

Hinged dissections exist.
Proceedings of the 24th ACM Symposium on Computational Geometry, 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 and Combinatorics, 2007

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

Geodesic Ham-Sandwich Cuts.
Discrete & Computational Geometry, 2007

Plane Embeddings of Planar Graph Metrics.
Discrete & Computational Geometry, 2007

The Stackelberg Minimum Spanning Tree Game
CoRR, 2007

Hinged Dissections Exist
CoRR, 2007

Generalized D-Forms Have No Spurious Creases
CoRR, 2007

The Distance Geometry of Music
CoRR, 2007

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

The Stackelberg Minimum Spanning Tree Game.
Proceedings of the Algorithms and Data Structures, 10th International Workshop, 2007

Scheduling to minimize gaps and power consumption.
Proceedings of the SPAA 2007: Proceedings of the 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2007

Minimizing movement.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Approximation algorithms via contraction decomposition.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

The price of anarchy in network creation games.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, 2007

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

Linear Reconfiguration of Cube-Style Modular Robots.
Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

An Optimal Decomposition Algorithm for Tree Edit Distance.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

Staged Self-assembly: Nanomanufacture of Arbitrary Shapes with O (1) Glues.
Proceedings of the DNA Computing, 13th International Meeting on DNA Computing, 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, Gyeongju, 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. Discrete 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.
Discrete & Computational Geometry, 2006

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

Locked and Unlocked Chains of Planar Shapes
CoRR, 2006

EpiChord: Parallelizing the Chord lookup algorithm with reactive routing state management.
Computer Communications, 2006

Geometric Restrictions on Producible Polygonal Protein Chains.
Algorithmica, 2006

Combination can be hard: approximability of the unique coverage problem.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 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 (lat. On Dynamic Dictionaries Using Little Space).
Proceedings of the LATIN 2006: Theoretical Informatics, 2006

Optimally Adaptive Integration of Univariate Lipschitz Functions.
Proceedings of the LATIN 2006: Theoretical Informatics, 2006

Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams.
Proceedings of the LATIN 2006: Theoretical Informatics, 2006

Approximability of Partitioning Graphs with Supply and Demand.
Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction.
Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

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

Necklaces, Convolutions, and X + Y.
Proceedings of the Algorithms, 2006

Refolding planar polygons.
Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

Locked and unlocked chains of planar shapes.
Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

Plane embeddings of planar graph metrics.
Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

Voronoi game on graphs and its complexity.
Proceedings of the 2006 IEEE Symposium on Computational Intelligence and Games (CIG06), 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 (k, r)-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 H-minor-free graphs.
J. ACM, 2005

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

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

Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries.
Discrete & Computational Geometry, 2005

Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams
CoRR, 2005

De Dictionariis Dynamicis Pauco Spatio Utentibus
CoRR, 2005

Bidimensionality, Map Graphs, and Grid Minors
CoRR, 2005

Logarithmic Lower Bounds in the Cell-Probe Model
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 Inf., 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

Subquadratic Algorithms for 3SUM.
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

Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics.
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. Discrete 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. Geometry Appl., 2004

Tight bounds on maximal and maximum matchings.
Discrete Mathematics, 2004

Fun-Sort--or the chaos of unordered binary search.
Discrete Applied Mathematics, 2004

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

Communication-Aware Processor Allocation for Supercomputers
CoRR, 2004

Online Searching with Turn Cost
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

Retroactive data structures.
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 H-minor-free graphs.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Refolding planar polygons.
Proceedings of the 31. International Conference on Computer Graphics and Interactive Techniques, 2004

The Bidimensional Theory of Bounded-Genus Graphs.
Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

Bidimensional Parameters and Local Treewidth.
Proceedings of the LATIN 2004: Theoretical Informatics, 2004

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

Grid Vertex-Unfolding Orthostacks.
Proceedings of the Discrete and Computational Geometry, Japanese Conference, 2004

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

EpiChord: parallelizing the chord lookup algorithm with reactive routing state management.
Proceedings of the 12th IEEE International Conference on Networks, 2004

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

Dynamic Optimality - Almost.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 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

Separating point sets in polygonal environments.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

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

Geodesic ham-sandwich cuts.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

Optimal adaptive algorithms for finding the nearest and farthest point on a parametric black-box curve.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

Low-dimensional embedding with extra information.
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

Blowing Up Polygonal Linkages.
Discrete & Computational Geometry, 2003

Optimal Covering Tours with Turn Costs
CoRR, 2003

Optimal Adaptive Algorithms for Finding the Nearest and Farthest Point on a Parametric Black-Box Curve
CoRR, 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.
Bioinformatics, 2003

Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries.
Proceedings of the Algorithms and Data Structures, 8th International Workshop, 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

Geometric Restrictions on Producible Polygonal Protein Chains.
Proceedings of the Algorithms and Computation, 14th International Symposium, 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

Planar Embeddings of Graphs with Specified Edge Lengths.
Proceedings of the Graph Drawing, 11th International Symposium, 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

Finding Hidden Independent Sets in Interval Graphs.
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. Geometry Appl., 2002

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

Balanced k-colorings.
Discrete Mathematics, 2002

A note on reconfiguring tree linkages: trees can lock.
Discrete Applied Mathematics, 2002

Efficient Tree Layout in a Multilevel Memory Hierarchy
CoRR, 2002

Solitaire Clobber
CoRR, 2002

Coin-Moving Puzzles
CoRR, 2002

Open Problems from CCCG 2002
CoRR, 2002

Long Proteins with Unique Optimal Foldings in the H-P Model
CoRR, 2002

Tetris is Hard, Even to Approximate
CoRR, 2002

PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation
CoRR, 2002

K-ary Clustering with Optimal Leaf Ordering for Gene Expression Data.
Proceedings of the Algorithms in Bioinformatics, Second International Workshop, 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 K3, 3-Minor-Free or K5-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, Barcelona, 2002

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

Solitaire Clobber.
Proceedings of the Computers and Games, Third International Conference, CG 2002, Edmonton, 2002

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

Proximate point searching.
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

Computing signed permutations of polygons.
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 Distrib. Syst., 2001

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

Locked and Unlocked Polygonal Chains in Three Dimensions.
Discrete & Computational Geometry, 2001

Vertex-Unfoldings of Simplicial Manifolds
CoRR, 2001

Enumerating Foldings and Unfoldings between Polygons and Polytopes
CoRR, 2001

Vertex-Unfoldings of Simplicial Polyhedra
CoRR, 2001

The Complexity of Clickomania
CoRR, 2001

Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
CoRR, 2001

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

Reconfiguring convex polygons.
Comput. Geom., 2001

When Can You Fold a Map?
Proceedings of the Algorithms and Data Structures, 7th International Workshop, 2001

On universally easy classes for NP-complete problems.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

A linear lower bound on index size for text retrieval.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Optimal covering tours with turn costs.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

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

Tight Bounds on Maximal and Maximum Matchings.
Proceedings of the Algorithms and Computation, 12th International Symposium, 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
Computational Geometry Column 37.
Int. J. Comput. Geometry Appl., 2000

When Can You Fold a Map?
CoRR, 2000

Flipturning polygons
CoRR, 2000

PushPush and Push-1 are NP-hard in 2D
CoRR, 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

Balanced k-Colorings.
Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

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

Online Routing in Convex Subdivisions.
Proceedings of the Algorithms and Computation, 11th International Conference, 2000

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

Cache-Oblivious B-Trees.
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

Polygons Cuttable by a Circular Saw.
Proceedings of the 12th Canadian Conference on Computational Geometry, 2000

Reconfiguring Convex Polygons.
Proceedings of the 12th Canadian Conference on Computational Geometry, 2000

1999
Computational geometry column 37.
SIGACT News, 1999

On Reconfiguring Tree Linkages: Trees can Lock
CoRR, 1999

Locked and Unlocked Polygonal Chains in 3D
CoRR, 1999

Computational Geometry Column 37
CoRR, 1999

Ununfoldable Polyhedra with Convex Faces
CoRR, 1999

Hinged Dissection of Polyominoes and Polyforms
CoRR, 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

Efficient Algorithms for Petersen's Matching Theorem.
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

Folding Flat Silhouettes and Wrapping Polyhedral Packages: New Results in Computational Origami.
Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 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
Locked and Unlocked Polygonal Chains in 3D
CoRR, 1998

C to Java: Converting Pointers into References.
Concurrency - Practice and Experience, 1998

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

Protocols for Non-Deterministic Communication over Synchronous Channels.
IPPS/SPDP, 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.
International Journal of High Speed Computing, 1996


  Loading...