情報処理学会 第87回全国大会

7K-02
通信・メモリ制約を持つ同期式通信のための平面グラフ上の頂点彩色問題に対する定数近似アルゴリズム
○佐藤 空,山田敏則(埼玉大)
ノード間に専用の通信路を持たない同期式通信において安定して通信を行うためには,メッセージ衝突とメッセージ競合を避けることが必要となる.ここでメッセージ衝突とは限界を超えた数の隣接ノードから同時にメッセージを受信することをいい,メッセージ競合とは隣接ノード同士が同時にメッセージを送信することをいう.このような通信を背景にした次の彩色問題を考える:グラフGと正の整数mが与えられたとき,隣接する頂点どうしに同じ色を与えず,ある頂点に隣接する頂点の中で同じ色を持つ頂点が高々m個であるように,最小個の色でGの頂点を彩色せよ.Gが木であるときにはこの問題が多項式時間で求められることが知られている.小文では,Gが平面的グラフであるときに,この問題に対する9-近似アルゴリズムを提案する。