| Item type |
SIG Technical Reports(1) |
| 公開日 |
2016-06-17 |
| タイトル |
|
|
タイトル |
媒介中心性を考慮したシュタイナー木構築法 |
| タイトル |
|
|
言語 |
en |
|
タイトル |
A Construction Method for the Steiner Tree Problem Based on Betweenness Centrality |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
日本工業大学大学院工学研究科電子情報メディア工学専攻 |
| 著者所属 |
|
|
|
日本工業大学工学部電気電子工学科 |
| 著者所属 |
|
|
|
日本工業大学工学部電気電子工学科 |
| 著者名 |
藤田, 実沙
木村, 貴幸
神野, 健哉
|
| 著者名(英) |
Misa, Fujita
Takayuki, Kimura
Kenya, Jin'no
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
ノード V，エッジ E，エッジのコスト関数 c からなる無向グラフ G = (V,E,c) とターミナル T ∈ V が与えられたとき，T の全てを連結する閉路のない部分グラフをシュタイナー木と呼ぶ．特に，入力されたグラフに対する最小コストのシュタイナー木を求める問題をシュタイナー木問題と呼ぶ．シュタイナー木問題は NP 完全な組合せ最適化問題であるため，近似解を求めるのが一般的である．本研究では，シュタイナー木問題に対してネットワーク中心性を考慮した解構築手法を提案する．ネットワーク中心性のうち媒介中心性は，ネットワーク中の全最短経路に多く使用されるノードやエッジを中心とするネットワーク評価指標である．媒介中心性が高いノードやエッジをシュタイナー木に含むことにより，コストの小さいシュタイナー木を得ることができると考えられる．本稿では，媒介中心性を考慮したシュタイナー木構築手法の性能を，ベンチマーク問題を用いて評価する．数値実験の結果から，媒介中心性を考慮することにより，従来法と比較してコストの小さいシュタイナー木を得られることを確認した． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
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. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2016-AL-158,
号 20,
p. 1-6,
発行日 2016-06-17
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL16158020.pdf (928.2 kB)
