抄録
CA-001
単位円グラフ上での高連結度支配集合問題に対する主双対近似アルゴリズム
福永拓郎(NII/JST, ERATO, 河原林巨大グラフプロジェクト)
無向グラフのk連結m支配集合とは,頂点集合Vの部分集合Sのうち,次の2つの条件を満たす者のことである.(i) Sに含まれない各頂点が,Sに含まれるm個以上の頂点に隣接する.(ii) Sによって誘導される部分グラフがk連結である.ユニットディスクグラフ上の重み最小のk連結m支配集合を求める最適化問題は,無線アドホックネットワークの仮想バックボーン構築を応用として持つことから盛んに研究されている.本論文ではこの問題に対し,m \geq k の場合にO(k2 log k)近似を達成する主双対近似アルゴリズムを与える.