講演抄録/キーワード |
講演名 |
2008-05-13 13:55
3 < n/k < 4に対する平面グラフのn/k-彩色問題のNP完全性 ○庄司將一・上嶋章宏(阪電通大) COMP2008-11 |
抄録 |
(和) |
本稿では,$H$-彩色問題($H$は単純無向グラフ)の部分問題である$n/k$-彩色問題($n$, $k$は$n/k \ge 2$である自然数)について考える.一般のグラフに対する$n/k$-彩色問題の計算複雑さは,$H$-彩色問題に関する既存結果から明らかである.一方,平面グラフに対する$n/k$-彩色問題の計算複雑さは未解決である.本問題は,$2 < n/k < 3$および$3 < n/k < 4$である任意の$n/k$に対し計算複雑さを解析することで充分であり,$2 < n/k < 3$である$n/k$でのNP完全性はすでに証明した.本稿では,$3 < n/k < 4$である任意の$n/k$に対するNP完全性を示す. |
(英) |
This report considers the $n/k$-coloring problem, which is a subproblem for the $H$-coloring problem, where $H$ is a simple undirected graph and $n$, $k$ are positive integers with $n/k \ge 2$. The computational complexities of $n/k$-coloring problems on general graphs can be obtained directly from the prevoius results concerning $H$-coloring problems. However, the complexities of the problems on \textit{planar graphs} are still open. The analysis for any fixed $n/k$ with $2 < n/k < 3$ or $3 < n/k < 4$ is sufficient to prove that the problems on planar graphs are NP-complete, and NP-completeness of the problems with $2 < n/k < 3$ has been shown in our previous works. This report proves that the problems with $3 < n/k < 4$ are NP-complete. |
キーワード |
(和) |
$H$-彩色 / $n/k$-彩色 / NP完全 / 平面グラフ / / / / |
(英) |
$H$-coloring / $n/k$-coloring / NP-complete / planar graph / / / / |
文献情報 |
信学技報, vol. 108, no. 29, COMP2008-11, pp. 25-32, 2008年5月. |
資料番号 |
COMP2008-11 |
発行日 |
2008-05-06 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2008-11 |