シーケンシャルな交換による色付きトークン整列問題の計算複雑さ

• Item type: SIG Technical Reports(1)
• 公開日: 2016-06-17
• タイトル: シーケンシャルな交換による色付きトークン整列問題の計算複雑さ
• タイトル / 言語: en
• タイトル: Computational Complexity of Sequential Token Swapping Problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 岩手大学
• 著者所属: マサチューセッツ工科大学
• 著者所属: 埼玉大学
• 著者所属: 東京大学
• 著者所属: 群馬大学
• 著者所属: 電気通信大学
• 著者所属: 神戸大学
• 著者所属: 東北大学
• 著者所属: 北陸先端科学技術大学院大学
• 著者所属: 国立情報学研究所
• 著者所属(英): en
• 著者所属(英): Iwate University
• 著者所属(英): en
• 著者所属(英): Massachusetts Institute of Technology
• 著者所属(英): en
• 著者所属(英): Saitama University
• 著者所属(英): en
• 著者所属(英): University of Tokyo
• 著者所属(英): en
• 著者所属(英): Gunma University
• 著者所属(英): en
• 著者所属(英): University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): Kobe University
• 著者所属(英): en
• 著者所属(英): Tohoku University
• 著者所属(英): en
• 著者所属(英): Japan Advanced Institute of Science and Technology
• 著者所属(英): en
• 著者所属(英): National Institute of Informatics
• 著者名: 山中, 克久; エリック, ドメイン; 堀山, 貴史; 河村, 彰星; 中野, 眞一; 岡本, 吉央; 斎藤, 寿樹; 鈴木, 顕; 上原, 隆平; 宇野, 毅明
• 著者名(英): Katsuhisa, Yamanaka; Erik, D. Demaine; Takashi, Horiyama; Akitoshi, Kawamura; Shin-ichi, Nakano; Yoshio, Okamoto; Toshiki, Saitoh; Akira, Suzuki; Ryuhei, Uehara; Takeaki, Uno
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 連結なグラフの頂点上に配置されたトークンを指定された頂点に移動するパズルを考える．各トークンは異なる頂点に配置されており，複数個の目標頂点が指定されている．グラフのパスに沿って “シーケンシャル” にトークンを交換することにより，全てのトークンを目標の頂点に配置させる． このパズルは 15 パズルの変種であり，O(n3) 回のトークンの交換で （解が存在するならば） 解くことができる．本論文では， トークンの最小交換回数を求める問題を考える． まず， この問題の近似困難性を示し，続いて，木と完全グラフに対して多項式時間解法を与える．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2016-AL-158, 号 17, p. 1-7, 発行日 2016-06-17
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会