| 大会名称 |
| 2009年 情報科学技術フォーラム(FIT) |
| 大会コ－ド |
| F |
| 開催年 |
|
2009
|
| 発行日 |
|
2009/8/20
|
| セッション番号 |
|
6A
|
| セッション名 |
|
グラフ・ネットワーク
|
| 講演日 |
|
2009/09/04
|
| 講演場所(会議室等) |
|
A会場（9号館1F 911教室）
|
| 講演番号 |
|
A-025
|
| タイトル |
|
Finding Reconfigurations between List Edge-Colorings of a Graph
|
| 著者名 |
|
Ito Takehiro, Kaminski Marcin, Demaine Erik D.,
|
| キーワード |
|
リスト辺彩色, 再構成問題, 木, 平面的グラフ
|
| 抄録 |
We study the problem of reconfiguring one list edge-coloring of a graph into another list edge-coloring by changing one edge color at a time, while at all times maintaining a list edge-coloring, given a list of allowed colors for each edge. First we show that this problem is PSPACE-complete. Then we consider the problem restricted to trees. We show that any list edge-coloring can be transformed into any other under the sufficient condition that the number of allowed colors for each edge is strictly larger than the degrees of both its endpoints. This sufficient condition is best possible in some sense. Our proof yields a polynomial-time algorithm that finds a transformation between two given list edge-colorings of a tree.
|
| 本文pdf |
|
PDF download (129.4KB)
|
