| 講演抄録／キーワード |
| 講演名 |
2005-03-18 15:25
比較可能 + ke グラフの彩色問題の計算量
○東出賢一・武永康彦（電通大） |
| 抄録 |
（和） |
比較可能+keグラフとは、比較可能グラフに辺を高々k本加えたグラフである。本稿では、kを定数としたときの比較可能+keグラフの彩色問題の計算量を考える。まず、比較可能+1eグラフの彩色問題が多項式時間で解けることを示す。そして、3SAT問題から比較可能+2eグラフの彩色問題への多項式時間帰着を示し、比較可能+2eグラフの彩色問題がNP完全であることを示す。 |
| （英） |
A comparability+ke graph is a graph that can be obtained from a comparability graph by adding at most k edges. In this report, we consider the complexity of coloring comparability+ke graphs. We show that on comparability+1e graphs, coloring problem can be solved in polynomial time. We also show that coloring comparability+2e graphs is NP-complete by a reduction from 3SAT. |
| キーワード |
（和） |
比較可能グラフ / 頂点彩色問題 / パラメータ付き計算量 / / / / / |
| （英） |
comparability graph / vertex coloring / parameterized complexity / / / / / |
| 文献情報 |
信学技報, vol. 104, no. 743, COMP2004-82, pp. 71-77, 2005年3月. |
| 資料番号 |
COMP2004-82 |
| 発行日 |
2005-03-11 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|