トークン整列問題への誘い－あみだくじをグラフヘー般化

• Item type: SIG Technical Reports(1)
• 公開日: 2016-11-17
• タイトル: トークン整列問題への誘い－あみだくじをグラフヘー般化
• タイトル / 言語: en
• タイトル: Introduction to Token Swapping Problem:An Generalization of Amidakuji
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 招待講演
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 岩手大学理工学部
• 著者所属(英): en
• 著者所属(英): Faculty of Science and Engineering, Iwate University
• 著者名: 山中, 克久
• 著者名(英): Katsuhisa, Ymanaka
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 連結なグラフの頂点上に配置されたトークンを指定された頂点に移動するパズルを考える．グラフはn個の頂点をもち， トークンもn個存在する．各トークンは，互いに異なる頂点に配置され，互いに異なる頂点が目的地として指定されている．隣接する頂点に配置されている 2 つのトークンを交換することを繰り返して，全てのトークンを目的の頂点へ移動させることが目標である． このパズルは，あみだくじ （互換による置換の分解） を， グラフ上の整列問題と解釈することで考案された問題である．本発表では，このパズルを，最小の交換回数で解く問題について解説する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Consider a puzzle consisting of n tokens on an n-vertex graph, where each token has a distinct starting vertex and a distinct target vertex it wants to reach, and the only allowed transformation is to swap the tokens on adjacent vertices. This puzzle is derived by extending Japanese traditional lottery, called "Amidakuji" to a sorting problem on a graph. We investigate how to solve the puzzle with the minimum number of token swaps.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2016-AL-160, 号 18, p. 1-1, 発行日 2016-11-17
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会