文献

J-GLOBAL ID：201402281671868960   整理番号：14A1500223

グラフのリスト点彩色の遷移

Reconfiguration of List Colorings in a Graph

著者 (3件)： HATANAKA Tatsuhiko (Tohoku Univ., Sendai, JPN) ,  ITO Takehiro (Tohoku Univ., Sendai, JPN) ,  ZHOU Xiao (Tohoku Univ., Sendai, JPN)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 114  号： 238(COMP2014 25-31)  ページ： 19-24  発行年： 2014年10月01日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： グラフの各点には,その点に割り当てることができる色のリストが与えられているとする。本稿では,1つのリスト点彩色から同じグラフの別のリスト点彩色へ,段階的に遷移できるかどうか判定する問題を扱う。ただし,一度にはただ1点の色のみ変更することができ,遷移の過程でも常にリスト点彩色でなければならない。この問題は平面2部グラフにおいてPSPACE完全であることが知られている。本稿では,この問題をグラフのパス幅の観点から解析する。はじめに,この問題はパス幅2のグラフでさえPSPACE完全であることを示す。一方で,パス幅1のグラフに対しては,多項式時間で解けることを示す。(著者抄録)

シソーラス用語： アルゴリズム ,  *発色 ,  *状態 ,  計算理論 ,  時間 ,  可到達性 ,  *グラフ ,  グラフアルゴリズム ,  *遷移
準シソーラス用語： *彩色 ,  多項式時間 ,  到達可能性

分類 (1件)： グラフ理論基礎  (IA02020S)

引用文献 (25件)：

• Bonamy, M., Johnson, M., Lignos, I., Patel, V., Paulusma, D.: Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. J. Combinatorial Optimization 27, pp. 132-143 (2014)
• Bonamy, M., Bousquet, N.: Recoloring bounded treewidth graphs. Electronic Notes in Discrete Mathematics 44, pp. 257-262(2013)
• Bonsma, P.: Rerouting shortest paths in planar graphs. Proc. of FSTTCS 2012, pp. 337-349 (2012)
• Bonsma, P.: The complexity of rerouting shortest paths. Theoretical Computer Science 510, pp.1-12(2013)
• Bonsma, P., Cereceda, L.: Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theoretical Computer Science 410, pp. 5215-5226 (2009)

タイトルに関連する用語 (4件)： グラフ ,  リスト ,  彩色 ,  遷移