Computational Complexity of Piano-Hinged Dissections
スポンサーリンク
概要
- 論文の詳細を見る
We prove NP-completeness of deciding whether a given loop of colored right isosceles triangles, hinged together at edges, can be folded into a specified rectangular three-color pattern. By contrast, the same problem becomes polynomially solvable with one color or when the target shape is a tree-shaped polyomino.
- 2013-05-10
著者
-
Uehara Ryuhei
School Of Information Science Japan Advanced Institute Of Science And Technology
-
Ryuhei Uehara
School Of Information Science Jaist
-
Takashi Horiyama
Information Technology Center, Saitama University
-
Zachary Abel
MIT Department of Mathematics
関連論文
- Graph Orientation Problems for Multiple st-Reachability
- Efficient Enumeration of All Pseudoline Arrangements
- The Complexity of Free Flood Filling Games
- Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem
- On the number of reduced trees, cographs, and series-parallel graphs by compression
- Reconstruction Algorithms for Permutation Graphs and Distance-Hereditary Graphs
- NP-completeness of generalized Kaboozle
- Computational Complexity of Piano-Hinged Dissections
- Finding a Hamiltonian Path in a Cube with Specified Turns is Hard (Preprint)
- Bumpy Pyramid Folding Problem
- Zipper Unfolding of Domes and Prismoids
- Polynomial-Time Algorithms for Subgraph Isomorphism in Small Graph Classes of Perfect Graphs
- Intersection dimension of bipartite graphs
- FPT algorithms for Token Jumping on Graphs
- Common Unfolding of Regular Tetrahedron and Johnson-Zalgaller Solid