抄録

A-015
最小最短パススタイナー木に対する近似アルゴリズム

ワイヤレスメッシュネットワークは，ルーター間をマルチホップで通信を行うことにより，低コストで広範囲の通信が可能である．本研究ではマルチキャスト通信について考える．ネットワーク上のマルチキャスト通信のルーティングは，グラフ上のスタイナー木で表すことができる．また，送信元と受信先ノードを結ぶ経路の長さを短くする最短パス木を構成することで遅延を減少させることができる．さらに，スタイナー木の内部ノードの数を減らすことで，通信回数を減らすことができ，結果としてスループットが増大する．そこで，本研究では，グラフ上の内部ノード数最小の最短パススタイナー木を求める問題を考える．