{"id":211504,"created":"2025-01-19T01:12:39.130256+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00211504","sets":["1164:5305:10533:10609"]},"path":["10609"],"owner":"44499","recid":"211504","title":["王将グラフ上での順次交換による色付きドロップ整列の計算量"],"pubdate":{"attribute_name":"公開日","attribute_value":"2021-06-12"},"_buckets":{"deposit":"5205e29e-52bb-4477-b396-1cdc58a151d3"},"_deposit":{"id":"211504","pid":{"type":"depid","value":"211504","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"王将グラフ上での順次交換による色付きドロップ整列の計算量","author_link":["537433","537434","537431","537432"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"王将グラフ上での順次交換による色付きドロップ整列の計算量"},{"subitem_title":"Sequentially Swapping Colored Tokens on King's Graphs","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"ゲームの理論","subitem_subject_scheme":"Other"}]},"item_type_id":"4","publish_date":"2021-06-12","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"名古屋大学情報学部"},{"subitem_text_value":"名古屋大学未来社会創造機構"},{"subitem_text_value":"名古屋大学大学院情報学研究科"},{"subitem_text_value":"名古屋大学大学院情報学研究科"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/211504/files/IPSJ-GI21046014.pdf","label":"IPSJ-GI21046014.pdf"},"date":[{"dateType":"Available","dateValue":"2023-06-12"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-GI21046014.pdf","filesize":[{"value":"477.6 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"18"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"fd53a772-50ef-419a-ab35-50b8ce936efa","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2021 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"岡田, 優斗"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"木谷, 裕紀"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"大舘, 陽太"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"小野, 廣隆"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AA11362144","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"2188-8736","subitem_source_identifier_type":"ISSN"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"王将グラフとは王将の動きをもとに定義されたグラフであり，いわゆるグリッドに斜辺を足した形をとる．本研究では王将グラフの各頂点に置かれた色付きドロップを初期配置から最終配置に整列させる問題を考える．ただし，ドロップの移動はグラフの適当な歩（walk）上でドロップを順次交換する形をとる．2×2 以上の王将グラフ上では十分長い歩に沿って順次交換を行えば，任意の初期配置からドロップ各色の色数が等しい任意の最終配置へ整列させることができることが知られている．本研究では，そのような歩長のオーダー的にタイトな上界を与える．またドロップが 2 色の場合，入力 k に対して歩長 k 以下の順次交換で目的を達成可能かの判定が NP 完全であることなどを示す．なおこの問題は，モバイル端末ゲーム，パズル&ドラゴンズでのドロップ移動をモデル化したものである．","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"A king's graph is a graph that represents all legal moves of the king piece on a chessboard, and it forms a grid added with diagonal edges. In this paper, we consider to relocate colored drops on the vertices of a king's graph to a given goal configuration, where drops are moved along a walk in a sequentially swapped manner. Such relocation is always possible from an arbitrary drop configuration to another arbitrary legal drop configuration for king's graphs of size at least 2 × 2 if we use a sufficiently long walk. We give an upper bound on the length of such a walk, which is tight in terms of order. Furthermore, we show that it is NP-complete to decide for given positive integer k whether there exists a walk with length at most k so as to relocate 2-colored drops from an initial configuration to a goal configuration. In passing, sequentially swapping drops models a rule of drop moves of a mobile device game called “Puzzle & Dragons”.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"8","bibliographic_titles":[{"bibliographic_title":"研究報告ゲーム情報学（GI）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2021-06-12","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"14","bibliographicVolumeNumber":"2021-GI-46"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"updated":"2025-01-19T17:46:42.618076+00:00","links":{}}