| 講演名 | 2018-12-12 Linear-Time Algorithms for the Generalized Coloring Reconfiguration Problem 大澤 弘基(東北大), 鈴木 顕(東北大), 伊藤 健洋(東北大), 周 暁(東北大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 彩色遷移問題は，最もよく研究されている遷移問題である．この問題では，高々$k$色を用いたグラフの（頂点）彩色が$2$つ与えられたとき，一度に$1$頂点のみの色を変更する操作を繰り返して，一方の彩色から他方の彩色へ到達できるか判定したい．ただし，遷移の過程でも，常に適切な彩色を保持しなければならない．彩色遷移問題は，$kle3$であれば多項式時間で解ける一方で，$k ge 4$の定数ではPSPACE完全であることが知られている．本稿では，この問題を色変更制約の観点から解析する．色変更制約は，グラフ$R$として与えられる．ここで，$R$の頂点集合は（$k$色からなる）色集合に対応し，$R$の各辺は直接変更できる色のペアを表現している．本稿では，$R$が最大次数$2$の場合に，この一般化された彩色遷移問題が線形時間で解けることを示す． |
| 抄録(英) | {sc Coloring reconfiguration} is one of the most well-studied reconfiguration problems. In the problem, we are given two proper (vertex-)colorings of a graph using at most $k$ colors, and asked to determine whether there exists a transform between them by recoloring only a single vertex at a time, while maintaining a proper coloring. It is known that this problem is solvable in polynomial time if $kleq3$, while is PSPACE-complete for a fixed $kgeq4$. In this paper, we study this problem from a viewpoint of recolorability constraints, which is given in terms of a graph $R$ whose vertices are colors, and each edge represents a pair of colors that can be recolored directly. In this paper, we show that this generalized problem can be solved in linear time if $R$ is of maximum degree at most two. |
| キーワード(和) | 組合せ遷移 / グラフアルゴリズム / グラフ彩色 |
| キーワード(英) | combinatorial reconfiguration / graph algorithm / graph coloring |
| 資料番号 | COMP2018-32 |
| 発行日 | 2018-12-05 (COMP) |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2018/12/12(から1日開催) |
| 開催地（和） | 東北大学 |
| 開催地（英） | Tohoku University |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 藤戸 敏弘(豊橋技科大) |
| 委員長氏名（英） | Toshihiro Fujito(Toyohashi Univ. of Tech.) |
| 副委員長氏名（和） | 中野 眞一(群馬大) |
| 副委員長氏名（英） | Shinichi Nakano(Gunma Univ.) |
| 幹事氏名（和） | 玉置 卓(京大) / 大舘 陽太(熊本大) |
| 幹事氏名（英） | Suguru Tamaki(Kyoto Univ.) / Yota Otachi(Kumamoto Univ) |
| 幹事補佐氏名（和） | 脊戸 和寿(成蹊大) |
| 幹事補佐氏名（英） | Kazuhisa Seto(Seikei Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | Linear-Time Algorithms for the Generalized Coloring Reconfiguration Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 組合せ遷移 / combinatorial reconfiguration |
| キーワード(2)（和/英） | グラフアルゴリズム / graph algorithm |
| キーワード(3)（和/英） | グラフ彩色 / graph coloring |
| 第 1 著者 氏名（和/英） | 大澤 弘基 / Hiroki Osawa |
| 第 1 著者 所属（和/英） | 東北大学(略称：東北大) Tohoku University(略称：Tohoku Univ.) |
| 第 2 著者 氏名（和/英） | 鈴木 顕 / Akira Suzuki |
| 第 2 著者 所属（和/英） | 東北大学(略称：東北大) Tohoku University(略称：Tohoku Univ.) |
| 第 3 著者 氏名（和/英） | 伊藤 健洋 / Takehiro Ito |
| 第 3 著者 所属（和/英） | 東北大学(略称：東北大) Tohoku University(略称：Tohoku Univ.) |
| 第 4 著者 氏名（和/英） | 周 暁 / Xiao Zhou |
| 第 4 著者 所属（和/英） | 東北大学(略称：東北大) Tohoku University(略称：Tohoku Univ.) |
| 発表年月日 | 2018-12-12 |
| 資料番号 | COMP2018-32 |
| 巻番号（vol） | vol.118 |
| 号番号（no） | COMP-356 |
| ページ範囲 | pp.7-14(COMP), |
| ページ数 | 8 |
| 発行日 | 2018-12-05 (COMP) |