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
著者
-
DEMAINE Erik
MIT Computer Science and Artificial Intelligence Laboratory
-
Demaine Martin
MIT Computer Science and Artificial Intelligence Laboratory
-
UEHARA Ryuhei
School of Information Science
-
Abel Zachary
MIT Department of Mathematics
-
HORIYAMA TAKASHI
Information Technology Center, Saitama University
-
UEHARA RYUHEI
School of Information Science, Japan Advanced Institute of Science and Technology(JAIST)
関連論文
- リスト辺彩色の再構成問題
- 需要点と供給点があるグラフの分割問題の近似可能性
- 再構成問題の計算複雑さ
- Bipartite powers of interval bigraphs
- A-025 Finding Reconfigurations between List Edge-Colorings of a Graph
- Longest Path Problems on Ptolemaic Graphs
- FOREWORD
- 部分集合和遷移問題の多項式時間近似スキーム
- Voronoi Game on a Path
- Hardness results and an exact exponential algorithm for the spanning tree congestion problem (コンピュテーション)
- NP-completeness of generalized Kaboozle
- Reconstruction Algorithms for Permutation Graphs and Distance-Hereditary Graphs
- Finding a Hamiltonian Path in a Cube with Specified Turns is Hard
- Computational Complexity of Piano-Hinged Dissections
- Reconstruction Algorithms for Permutation Graphs and Distance-Hereditary Graphs