@techreport{oai:ipsj.ixsq.nii.ac.jp:00164045,
 author = {藤田, 実沙 and 木村, 貴幸 and 神野, 健哉 and Misa, Fujita and Takayuki, Kimura and Kenya, Jin'no},
 issue = {20},
 month = {Jun},
 note = {ノード V，エッジ E，エッジのコスト関数 c からなる無向グラフ G = (V,E,c) とターミナル T ∈ V が与えられたとき，T の全てを連結する閉路のない部分グラフをシュタイナー木と呼ぶ．特に，入力されたグラフに対する最小コストのシュタイナー木を求める問題をシュタイナー木問題と呼ぶ．シュタイナー木問題は NP 完全な組合せ最適化問題であるため，近似解を求めるのが一般的である．本研究では，シュタイナー木問題に対してネットワーク中心性を考慮した解構築手法を提案する．ネットワーク中心性のうち媒介中心性は，ネットワーク中の全最短経路に多く使用されるノードやエッジを中心とするネットワーク評価指標である．媒介中心性が高いノードやエッジをシュタイナー木に含むことにより，コストの小さいシュタイナー木を得ることができると考えられる．本稿では，媒介中心性を考慮したシュタイナー木構築手法の性能を，ベンチマーク問題を用いて評価する．数値実験の結果から，媒介中心性を考慮することにより，従来法と比較してコストの小さいシュタイナー木を得られることを確認した．, Given an undirected weighted graph G = (V, E, c) and a set T ∈ V, where V is the set of nodes, E is the set of edges, c is a cost function, and T is a subset of terminal nodes, a subgraph that doesn't have a loop and connecting all of T is called a Steiner tree. Finding the smallest cost of the Steiner tree is called a Steiner tree problem in graphs. The Steiner tree problem in graphs is one of the NP-complete combinatorial optimization problems, approximation methods are then usually applied to obtain the small cost of Steiner tree. In this study, we propose a construction method for the Steiner tree problem in graphs using network centrality. Betweenness centrality is an example of the network centrality that shows how many times a node or an edge appears on the all of the shortest paths in the network. Therefore, if nodes or edges which have high betweenness centrality are included in the Steiner tree, obtained cost of the Steiner tree may become small. We then evaluate the performance of the proposed method by solving benchmark problems. Results of numerical simulations indicate that shorter Steiner trees are obtained using the betweenness centrality effectively.},
 title = {媒介中心性を考慮したシュタイナー木構築法},
 year = {2016}
}