Valid Orderings of Layers When Simple-Folding a Map

• Jia Yiyang

  University of Tsukuba

• Mitani Jun

  University of Tsukuba

• Uehara Ryuhei

  School of Information Science, JAIST

抄録

In this work, we consider a decision problem on whether an overlapping order of all the squares of an m × n map is valid under a particular context called simple folding. This problem belongs to the field of map folding. It is a variation of both the decision problem of valid orders of a 1 × n map under the context of simple folds and the decision problem of valid orders of an m × n map under the context of general folds. We provide a method and its corresponding linear-time algorithm to solve this problem, which is based on the construction of a directed graph representing the adjacency relations among squares.

収録刊行物

• Journal of Information Processing

  Journal of Information Processing 28 (0), 816-824, 2020

  一般社団法人 情報処理学会

キーワード

• map folding problem
• overlapping order
• <i>m</i> × <i>n</i> map
• linear-time algorithm

詳細情報

• CRID: 1390849931313316352
• NII論文ID: 130007956337
• DOI: 10.2197/ipsjjip.28.816
• ISSN: 18826652
• Web Site: https://www.jstage.jst.go.jp/article/ipsjjip/28/0/28_816/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可