A heuristic method for solving the Steiner tree problem in graphs using network centralities

被引：0
|
作者：
Fujita, Misa [1 ,2 ]
Shimada, Yutaka [3 ]
Kimura, Takayuki [4 ]
Ikeguchi, Tohru [2 ,5 ]
机构：
[1] Chukyo Univ, Sch Engn, Dept Elect & Elect Engn, Nagoya, Aichi, Japan
[2] Tokyo Univ Sci, Grad Sch Engn, Dept Management Sci, Katsushika Ku, Tokyo, Japan
[3] Saitama Univ, Grad Sch Sci & Engn, Sakura Ku, Saitama, Japan
[4] Nippon Inst Technol, Fac Fundamental Engn, Dept Elect Elect & Commun Engn, Miyashiro, Saitama, Japan
[5] Tokyo Univ Sci, Fac Engn, Dept Informat & Comp Technol, Katsushika Ku, Tokyo, Japan
来源：
PLOS ONE | 2024年 / 19卷 / 06期
基金：
日本学术振兴会;
关键词：
ALGORITHM; SEARCH;
D O I：
10.1371/journal.pone.0303764
中图分类号：
O [数理科学和化学]; P [天文学、地球科学]; Q [生物科学]; N [自然科学总论];
学科分类号：
07 ; 0710 ; 09 ;
摘要：
We propose a heuristic method of using network centralities for constructing small-weight Steiner trees in this paper. The Steiner tree problem in graphs is one of the practical NP-hard combinatorial optimization problems. Given a graph and a set of vertices called terminals in the graph, the objective of the Steiner tree problem in graphs is to find a minimum weight Steiner tree that is a tree containing all the terminals. Conventional construction methods make a Steiner tree based on the shortest paths between terminals. If these shortest paths are overlapped as much as possible, we can obtain a small-weight Steiner tree. Therefore, we proposed to use network centralities to distinguish which edges should be included to make a small-weight Steiner tree. Experimental results revealed that using the vertex or the edge betweenness centralities contributes to making small-weight Steiner trees.
引用
收藏
页数：16
相关论文
共 50 条
12345