三角格子点上の単位円グラフに対する多重彩色

概要

論文の詳細を見る
与えられた非負整数mとnに対して,P(m,n)={(ze_1+ye_2)|x∈{0,1,…,m-1},y∈{0,1,…,n-1}}と定義する.ここでe_1=^^<def>(1,0),e_2=^^<def>(1/2,√<3>/2)である,つまりP(m,n)は2次元平面上の三角格子点の部分集合を表す.P(m,n)を頂点集合とし,頂点間のユークリッド距離がd以下であるときに隣接と定義する無向グラフをT_<m,n>(d)とする.本稿ではT_<m,n>(d)がパーフェクトであるための必要条件と十分条件を議論する.具体的には,∀m∈Z_+に対してT_<m,n>(d)がパーフェクトである必要十分条件はd≧√<n^2-3n+3>であることを示す.非負整数頂点重みω∈Z^<P(m,n)>_+が与えられたとき,それぞれの頂点υ∈P(m,n)にω(υ)色が割り当てられ,隣接するどの頂点対も同じ色を共有しないようなP(m,n)への色の割り当てを(T_<m,n>(d),ω)の多重彩色という.本稿ではP(m,n)がパーフェクトであるときに(T_<m,n>(d),ω)を多重彩色する効率的な算法も示す.本稿の主な成果であるP(m,n)のパーフェクト性を利用すると一般の(T_<m,n>(d),ω)の多重彩色に対する多項式時間精度保証付き近似解法を構成できる.こうして構成した算法は高々α(d)ω+O(d^3)色を用いた多重彩色の解を算出する.ここでωは重み付きクリーク数である.d=1,√<3>,2,√<7>,3のとき,対応する近似率α(d)はそれぞれ(4/3),(5/3),(5/3),(7/4),(7/4)である.d>1のときα(d)≦(1+2/√<3>+(√^2<3>-3)/d)である.また本稿では,(T_<m,n>(d),ω)を(4/3)ω色で多重彩色できるか否か判定する問題はNP-完全であることを示す.
2004-10-14

三角格子点上の単位円グラフに対する多重彩色

スポンサーリンク

概要

著者

関連論文

スポンサーリンク