| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2018-12-12 10:25 Linear-Time Algorithms for the Generalized Coloring Reconfiguration Problem ○Hiroki Osawa・Akira Suzuki・Takehiro Ito・Xiao Zhou（Tohoku Univ.）  COMP2018-32 |
|
| 抄録 | （和） | 彩色遷移問題は，最もよく研究されている遷移問題である． この問題では，高々$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 / / / / / | |
| 文献情報 | 信学技報, vol. 118, no. 356, COMP2018-32, pp. 7-14, 2018年12月. | |
| 資料番号 | COMP2018-32 | |
| 発行日 | 2018-12-05 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2018-32 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2018-12-12 - 2018-12-12 |
| 開催地（和） | 東北大学 |
| 開催地（英） | Tohoku University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2018-12-COMP |
| 本文の言語 | 英語 |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | Linear-Time Algorithms for the Generalized Coloring Reconfiguration Problem |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 組合せ遷移 / combinatorial reconfiguration |
| キーワード(2)（和/英） | グラフアルゴリズム / graph algorithm |
| キーワード(3)（和/英） | グラフ彩色 / graph coloring |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第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.) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2018-12-12 10:25:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2018-32 |
| 巻番号（vol） | vol.118 |
| 号番号（no） | no.356 |
| ページ範囲 | pp.7-14 |
| ページ数 | 8 |
| 発行日 | 2018-12-05 (COMP) |
[研究会発表申込システムのトップページに戻る]