文献

J-GLOBAL ID：201502217377082663   整理番号：15A0910142

完全なスプリットグラフ上でのラベル付きトークンの交換

Swapping Labeled Tokens on Complete Split Graphs

著者 (4件)： YASUI Gaku (Iwate Univ., JPN) ,  ABE Kouta (Iwate Univ., JPN) ,  YAMANAKA Katsuhisa (Iwate Univ., JPN) ,  HIRAYAMA Takashi (Iwate Univ., JPN)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 115  号： 84(COMP2015 6-15)  ページ： 87-90  発行年： 2015年06月05日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： トークンの交換は,ソート問題の一般化の一種である。各頂点がトークンを有するグラフG=(V,E)が与えられると,隣接する頂点上で2つのトークンを繰返し交換することにより,トークンを目指す頂点へ移動させようとする。先に,山中等は,ツリーに対する多項式時間2近似アルゴリズム及び二部完全グラフに対する多項式時間厳密アルゴリズムを提案した。この論文では,完全なスプリットグラフに対する多項式時間厳密アルゴリズムを求めた。(翻訳著者抄録)

シソーラス用語： *トークン ,  *交換 ,  ソーティング ,  頂点 ,  部分グラフ ,  ラベリング ,  *完全グラフ ,  計算理論 ,  計算機アルゴリズム ,  分割
準シソーラス用語： グラフ分割 ,  ラベル付与 ,  二部グラフ ,  近似アルゴリズム ,  厳密アルゴリズム ,  多項式時間

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

引用文献 (3件)：

• Yamanaka, K., Demaine, E., Ito, T., Kawahara, J., Kiyomi, M., Okamoto, Y., Saitoh, T., Suzuki, A., Uchizawa, K. and Uno, T.: Swapping Labeled Tokens on Graphs, Theoretical Computer Science, accepted.
• Jerrum, M.: The Complexity Of Finding Minimum-length Generator Sequences, Theoretical Computer Science, Vol. 36, pp. 265-289 (1985).
• Heath, L. and Vergara, J.: Sorting by Short Swaps, Journal of Computational Biology, Vol. 10, pp. 775-789 (2003).

タイトルに関連する用語 (2件)： ラベル ,  トークン