Zig-Zag Numberlink is NP-Complete

• Item type: JInfP(1)
• 公開日: 2015-05-15
• タイトル: Zig-Zag Numberlink is NP-Complete
• タイトル / 言語: en
• タイトル: Zig-Zag Numberlink is NP-Complete
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [Special Issue of Recreational Discrete Mathematics] Nikoli, NP-hard, Number Link, Numberlink, puzzles, games, discrete mathematics
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Stanford University
• 著者所属: Massachusetts Institute of Technology
• 著者所属: Massachusetts Institute of Technology
• 著者所属: North Carolina State University
• 著者所属: RWTH Aachen University
• 著者所属: RWTH Aachen University
• 著者所属: North Carolina State University
• 著者所属(英): en
• 著者所属(英): Stanford University
• 著者所属(英): en
• 著者所属(英): Massachusetts Institute of Technology
• 著者所属(英): en
• 著者所属(英): Massachusetts Institute of Technology
• 著者所属(英): en
• 著者所属(英): North Carolina State University
• 著者所属(英): en
• 著者所属(英): RWTH Aachen University
• 著者所属(英): en
• 著者所属(英): RWTH Aachen University
• 著者所属(英): en
• 著者所属(英): North Carolina State University
• 著者名: Aaron, Adcock; ErikD., Demaine; MartinL., Demaine; MichaelP., O'Brien; Felix, Reidl; FernandoSanchez, Villaamil; BlairD., Sullivan
• 著者名(英): Aaron, Adcock; Erik, D.Demaine; Martin, L.Demaine; Michael, P.O'Brien; Felix, Reidl; Fernando, SanchezVillaamil; Blair, D.Sullivan
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: When can t terminal pairs in an m × n grid be connected by t vertex-disjoint paths that cover all vertices of the grid? We prove that this problem is NP-complete. Our hardness result can be compared to two previous NP-hardness proofs: Lynch's 1975 proof without the “cover all vertices” constraint, and Kotsuma and Takenaga's 2010 proof when the paths are restricted to have the fewest possible corners within their homotopy class. The latter restriction is a common form of the famous Nikoli puzzle Numberlink. Our problem is another common form of Numberlink, sometimes called Zig-Zag Numberlink and popularized by the smartphone app Flow Free.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: When can t terminal pairs in an m × n grid be connected by t vertex-disjoint paths that cover all vertices of the grid? We prove that this problem is NP-complete. Our hardness result can be compared to two previous NP-hardness proofs: Lynch's 1975 proof without the “cover all vertices” constraint, and Kotsuma and Takenaga's 2010 proof when the paths are restricted to have the fewest possible corners within their homotopy class. The latter restriction is a common form of the famous Nikoli puzzle Numberlink. Our problem is another common form of Numberlink, sometimes called Zig-Zag Numberlink and popularized by the smartphone app Flow Free.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA00700121
• 書誌情報: Journal of information processing; 巻 23, 号 3, p. 239-245, 発行日 2015-05-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-6652
• 出版者 / 言語: ja
• 出版者: 情報処理学会