講演抄録/キーワード |
講演名 |
2012-03-16 13:35
比較可能-keグラフの頂点彩色問題のパラメータ化計算量 ○斎藤 惇・武永康彦(電通大) COMP2011-51 |
抄録 |
(和) |
$\mathcal{F}-ke$グラフは、グラフ族$\mathcal{F}$のグラフから高々$k$本の辺を削除したグラフからなるグラフ族である。本研究では、比較可能$-ke$グラフの 頂点彩色問題 を考える。比較可能$-ke$グラフの頂点彩色問題のパラメータ化計算量が、比較可能グラフを表現するハッセ図の独立辺集合のサイズが$\frac{1}{k}\log n^{O(1)}$であるとき、$f(k)n^{O(1)}$となることを示す。また、exponential time hypothesisの下では、比較可能$-ke(k \geq 2)$グラフの頂点彩色問題のパラメータ化計算量が、比較可能グラフを表現するハッセ図の独立辺集合のサイズが$\frac{1}{k}\log n^{\omg (1)}$であるとき、$f(k)n^{O(1)}$とはならないことを示す。 |
(英) |
$\mathcal{F}-ke$ graphs is a class of graphs obtained by deleting at most $k$ edges from a graph in graph class $\mathcal{F}$. In this paper, we consider parameterized complexity of coloring comparability$-ke$ graphs. We show that vertex coloring of comparability$-ke$ graphs can be solved in $f(k)n^{O(1)}$ time for some function $f$ if the size of the maximum matching on the the Hasse diagram is $\frac{1}{k}\log n^{O(1)} $. We also prove that vertex coloring of comparability$-k$e graphs cannot be solved in $f(k)n^{O(1)}$ time for any function $f$ if the size of maximum matching on the Hasse diagram is $\frac{1}{k}\log n^{\omega (1)} $ under the exponential time hypothesis. |
キーワード |
(和) |
頂点彩色問題 / パラメータ化計算量 / 比較可能$-ke$グラフ / / / / / |
(英) |
vertex coloring / parameterized complexity / comparability-$ke$ graph / / / / / |
文献情報 |
信学技報, vol. 111, no. 494, COMP2011-51, pp. 31-38, 2012年3月. |
資料番号 |
COMP2011-51 |
発行日 |
2012-03-09 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2011-51 |