文献

J-GLOBAL ID：201502201541436290   整理番号：15A0910141

極大誘導木遷移問題

Reconfiguration Problem for Maximal Induced Trees

著者 (3件)： 和佐州洋 (北大 大学院情報科学研究科) ,  山中克久 (岩手大 工) ,  有村博紀 (北大 大学院情報科学研究科)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 115  号： 84(COMP2015 6-15)  ページ： 81-86  発行年： 2015年06月05日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 遷移問題とは,2つの実行可能解AとBが与えられたとき,Aに対して,繰り返し遷移ルールfを適用することで,AからBへの実行可能解の列(A₀=A,A₁,...,A_l=B)が存在するかを判定する問題である。ここで,各i=1,...,lに対して,A_i,は,A_i-1からfを適用することによって得られる実行可能解である。本稿では,実行可能解として極大誘導木に着目し,グラフの極大誘導木の遷移問題を考察した。主結果として,任意の入力グラフGと,Gの2つの極大誘導木SとTが与えられたとき,トークンジャンプとトークンスライディング,それぞれ遷移ルールのもとにおいて,極大誘導木の遷移問題がPSPACE完全であることを示した。(著者抄録)

シソーラス用語： 規則 ,  *遷移状態 ,  実現可能性 ,  解 ,  決定問題 ,  *スパンニング木 ,  誘導 ,  トークン ,  NP完全問題 ,  計算理論
準シソーラス用語： NP完全 ,  *極大木 ,  実行可能性 ,  遷移規則 ,  多項式時間 ,  判定問題

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

引用文献 (14件)：

• Cereceda, L., van den Heuvel, J. and Johnson, M.: Connectedness of the graph of vertex-colourings, Discrete Mathematics, Vol. 308, No. 5-6, pp. 913-919 (2008).
• Bonsma, P.: The complexity of rerouting shortest paths, Theoretical Computer Science, Vol. 510, pp. 1-12 (2013).
• Kamiński, M., Medvedev, P. and Milanič, M.: Complexity of independent set reconfigurability problems, Theoretical Computer Science, Vol. 439, pp. 9-15 (2012).
• Ito, T., Demaine, E. D., Harvey, N. J., Papadimitriou, C. H., Sideri, M., Uehara, R. and Uno, Y.: On the complexity of reconfiguration problems, Theoretical Computer Science, Vol. 412, No. 12-14, pp. 1054-1065 (2011).
• Derhy, N. and Picouleau, C.: Finding induced trees, Discrete Applied Mathematics, Vol. 157, No. 17, pp. 3552-3557 (2009).

タイトルに関連する用語 (3件)： 誘導 ,  木 ,  遷移