講演抄録/キーワード |
講演名 |
2014-10-08 14:45
Reconfiguration of List Colorings in a Graph ○Tatsuhiko Hatanaka・Takehiro Ito・Xiao Zhou(Tohoku Univ.) COMP2014-29 |
抄録 |
(和) |
グラフの各点には,その点に割り当てることができる色のリストが与えられているとする.本稿では,1つのリスト点彩色から同じグラフの別のリスト点彩色へ,段階的に遷移できるかどうか判定する問題を扱う.ただし,一度にはただ1点の色のみ変更することができ,遷移の過程でも常にリスト点彩色でなければならない.この問題は平面2部グラフにおいてPSPACE完全であることが知られている.本稿では,この問題をグラフのパス幅の観点から解析する.はじめに,この問題はパス幅2のグラフでさえPSPACE完全であることを示す.一方で,パス幅1のグラフに対しては,多項式時間で解けることを示す. |
(英) |
We study the problem of transforming one list (vertex) coloring of a graph into another list coloring by changing only one vertex color assignment at a time, while at all times maintaining a list coloring, given a list of allowed colors for each vertex. This problem is known to be PSPACE-complete for bipartite planar graphs. In this paper, we give precise analyses of the problem with respect to pathwidth. We first show that the problem remains PSPACE-complete even for graphs with pathwidth two. In contrast, we then give a polynomial-time algorithm to solve the problem for graphs with pathwidth one. |
キーワード |
(和) |
グラフアルゴリズム / リスト点彩色 / パス幅 / PSPACE完全 / 解空間における到達可能性 / / / |
(英) |
graph algorithm / list coloring / pathwidth / PSPACE-complete / reachability on solution space / / / |
文献情報 |
信学技報, vol. 114, no. 238, COMP2014-29, pp. 19-24, 2014年10月. |
資料番号 |
COMP2014-29 |
発行日 |
2014-10-01 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2014-29 |