{"created":"2025-01-19T00:35:54.746842+00:00","updated":"2025-01-20T11:03:08.773278+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00164042","sets":["1164:2592:8452:8750"]},"path":["8750"],"owner":"11","recid":"164042","title":["シーケンシャルな交換による色付きトークン整列問題の計算複雑さ"],"pubdate":{"attribute_name":"公開日","attribute_value":"2016-06-17"},"_buckets":{"deposit":"bedb201f-9cc8-46e9-ac16-47032cec059b"},"_deposit":{"id":"164042","pid":{"type":"depid","value":"164042","revision_id":0},"owners":[11],"status":"published","created_by":11},"item_title":"シーケンシャルな交換による色付きトークン整列問題の計算複雑さ","author_link":["322590","322591","322597","322596","322588","322592","322600","322604","322594","322587","322599","322602","322601","322603","322589","322598","322605","322593","322586","322595"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"シーケンシャルな交換による色付きトークン整列問題の計算複雑さ"},{"subitem_title":"Computational Complexity of Sequential Token Swapping Problem","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2016-06-17","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"岩手大学"},{"subitem_text_value":"マサチューセッツ工科大学"},{"subitem_text_value":"埼玉大学"},{"subitem_text_value":"東京大学"},{"subitem_text_value":"群馬大学"},{"subitem_text_value":"電気通信大学"},{"subitem_text_value":"神戸大学"},{"subitem_text_value":"東北大学"},{"subitem_text_value":"北陸先端科学技術大学院大学"},{"subitem_text_value":"国立情報学研究所"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Iwate University","subitem_text_language":"en"},{"subitem_text_value":"Massachusetts Institute of Technology","subitem_text_language":"en"},{"subitem_text_value":"Saitama University","subitem_text_language":"en"},{"subitem_text_value":"University of Tokyo","subitem_text_language":"en"},{"subitem_text_value":"Gunma University","subitem_text_language":"en"},{"subitem_text_value":"University of Electro-Communications","subitem_text_language":"en"},{"subitem_text_value":"Kobe University","subitem_text_language":"en"},{"subitem_text_value":"Tohoku University","subitem_text_language":"en"},{"subitem_text_value":"Japan Advanced Institute of Science and Technology","subitem_text_language":"en"},{"subitem_text_value":"National Institute of Informatics","subitem_text_language":"en"}]},"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/164042/files/IPSJ-AL16158017.pdf","label":"IPSJ-AL16158017.pdf"},"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL16158017.pdf","filesize":[{"value":"321.3 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"9"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_login","version_id":"b51ffe6c-38b8-4aa0-92fd-4757ad6982ec","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2016 by the Institute of Electronics, Information and Communication Engineers This SIG report is only available to those in membership of the SIG."}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"山中, 克久"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"エリック, ドメイン"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"堀山, 貴史"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"河村, 彰星"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"中野, 眞一"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"岡本, 吉央"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"斎藤, 寿樹"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"鈴木, 顕"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"上原, 隆平"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"宇野, 毅明"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Katsuhisa, Yamanaka","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Erik, D. Demaine","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Takashi, Horiyama","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Akitoshi, Kawamura","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Shin-ichi, Nakano","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Yoshio, Okamoto","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Toshiki, Saitoh","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Akira, Suzuki","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Ryuhei, Uehara","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Takeaki, Uno","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN1009593X","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-8566","subitem_source_identifier_type":"ISSN"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"連結なグラフの頂点上に配置されたトークンを指定された頂点に移動するパズルを考える．各トークンは異なる頂点に配置されており，複数個の目標頂点が指定されている．グラフのパスに沿って “シーケンシャル” にトークンを交換することにより，全てのトークンを目標の頂点に配置させる． このパズルは 15 パズルの変種であり，O(n3) 回のトークンの交換で （解が存在するならば） 解くことができる．本論文では， トークンの最小交換回数を求める問題を考える． まず， この問題の近似困難性を示し，続いて，木と完全グラフに対して多項式時間解法を与える．","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"We consider a puzzle consisting of colored tokens on an n-vertex graph, where each token has a distinct starting vertex and a set of allowable target vertices for it to reach, and the only allowed transformation is to \"sequentially\" move the chosen token along a path of the graph by swapping it with other tokens on the path. This puzzle is a variation of the Fifteen Puzzle and is solvable in O(n3) token-swappings. We thus focus on the problem of minimizing the number of token-swappings to reach the target token-placement. We first give an inapproximability result of this problem, and then show polynomial-time algorithms on trees and complete graphs.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"7","bibliographic_titles":[{"bibliographic_title":"研究報告アルゴリズム（AL）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2016-06-17","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"17","bibliographicVolumeNumber":"2016-AL-158"}]},"relation_version_is_last":true,"weko_creator_id":"11"},"id":164042,"links":{}}