木のL(2,1)-ラベリングに対するO(n^<1.75>)時間アルゴリズム

概要

論文の詳細を見る
グラフのL(2,1)-ラベリングとは,頂点集合V(G)から非負整数への割当てfで,V(G)上のすべての隣接するxとyに対し,|f(x)-f(y)|≧2を満たし,すべての距離2で離れるxとyに対し,|f(x)-f(y)|≧1を満たすもののことを言う.k-L(2,1)-ラベリングとは,f:V(G)→{0,...,k}なる割当てfであり,L(2,1)-ラベリング問題とは,そのような最小のkを求める問題のことを言い,その最小値をλ(G)で表す.この問題はグラフの木幅が2のときでもNP困難であることが知られている.木はこの問題に対して多項式時間で求解可能な数少ないグラフクラスであるが,その計算量は小さくなく,最大次数Δ,頂点数nの木Tに対し,これまでO(Δ^<4.5>n)時間アルゴリズムしか知られていなかった.本論文では,まずλ(T)=Δ+1成立の既存の必要条件がΔ=Ω(√<n>)である木においては必要条件でもあることを示す.これによりΔ=Ω(√<n>)の場合にL(2,1)-ラベリングを求める線形時間アルゴリズムが得られる.次にλ(T)が任意の木に対してO(Δ^<1.5>n)時間で計算できることを示す.これらを組み合わせることにより,これまで知られていた最善の計算時間O(Δ^<4.5>n)を大幅に改善するO(n^<1.75>)時間アルゴリズムを提案する.
社団法人電子情報通信学会の論文
2008-05-06