著者

藤田 実沙 木村 貴幸 神野 健哉

雑誌

研究報告アルゴリズム(AL) (ISSN:21888566)

巻号頁・発行日

vol.2016-AL-158, no.20, pp.1-6, 2016-06-17

---

ノード V,エッジ E,エッジのコスト関数 c からなる無向グラフ G = (V,E,c) とターミナル T ∈ V が与えられたとき,T の全てを連結する閉路のない部分グラフをシュタイナー木と呼ぶ.特に,入力されたグラフに対する最小コストのシュタイナー木を求める問題をシュタイナー木問題と呼ぶ.シュタイナー木問題は NP 完全な組合せ最適化問題であるため,近似解を求めるのが一般的である.本研究では,シュタイナー木問題に対してネットワーク中心性を考慮した解構築手法を提案する.ネットワーク中心性のうち媒介中心性は,ネットワーク中の全最短経路に多く使用されるノードやエッジを中心とするネットワーク評価指標である.媒介中心性が高いノードやエッジをシュタイナー木に含むことにより,コストの小さいシュタイナー木を得ることができると考えられる.本稿では,媒介中心性を考慮したシュタイナー木構築手法の性能を,ベンチマーク問題を用いて評価する.数値実験の結果から,媒介中心性を考慮することにより,従来法と比較してコストの小さいシュタイナー木を得られることを確認した.