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 条
  • [41] Solving a production-routing problem with price-dependent demand using an outer approximation method
    Torkaman, Somayeh
    Jokar, Mohammad Reza Akbari
    Mutlu, Nevin
    Van Woensel, Tom
    COMPUTERS & OPERATIONS RESEARCH, 2020, 123
  • [42] A binary symmetric based hybrid meta-heuristic method for solving mixed integer unit commitment problem integrating with significant plug-in electric vehicles
    Yang, Zhile
    Li, Kang
    Guo, Yuanjun
    Feng, Shengzhong
    Niu, Qun
    Xue, Yusheng
    Foley, Aoife
    ENERGY, 2019, 170 : 889 - 905
  • [43] Solving time-varying inverse kinematics problem of wheeled mobile manipulators using Zhang neural network with exponential convergence
    Xiao, Lin
    Zhang, Yunong
    NONLINEAR DYNAMICS, 2014, 76 (02) : 1543 - 1559
  • [44] Solving the fuzzy shortest path problem using multi-criteria decision method based on vague similarity measure
    Dou, Yaling
    Zhu, Lichun
    Wang, Ho Simon
    APPLIED SOFT COMPUTING, 2012, 12 (06) : 1621 - 1631
  • [45] A method of solving a large-scale rolling batch scheduling problem in steel production using a variant of column generation
    Pan, Changchun
    Yang, G. K.
    COMPUTERS & INDUSTRIAL ENGINEERING, 2009, 56 (01) : 165 - 178
  • [46] A fuzzy logic-based method for solving the scheduling problem in the cloud environments using a non-dominated sorted algorithm
    Wakil, Karzan
    Badfar, Arshad
    Dehghani, Pooyan
    Sadati, Seyed Mojtaba Shoja
    Navimipour, Nima Jafari
    CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE, 2019, 31 (17)
  • [47] Solving multi-point problem for Volterra-Fredholm integro-differential equations using Dzhumabaev parameterization method
    Bakirova, Elmira A.
    Assanova, Anar T.
    Kadirbayeva, Zhazira M.
    OPEN MATHEMATICS, 2024, 22 (01):
  • [48] Solving the inverse kinematics problem of discretely actuated hyper-redundant manipulators using the multi-module searching method
    Motahari, Alireza
    ROBOTICA, 2024, 42 (03) : 911 - 930
  • [49] Solving cyclic train timetabling problem through model reformulation: Extended time-space network construct and Alternating Direction Method of Multipliers methods
    Zhang, Yongxiang
    Peng, Qiyuan
    Yao, Yu
    Zhang, Xin
    Zhou, Xuesong
    TRANSPORTATION RESEARCH PART B-METHODOLOGICAL, 2019, 128 : 344 - 379
  • [50] Solving Helmholtz equation with high wave number and ill-posed inverse problem using the multiple scales Trefftz collocation method
    Kuo, Chung-Lun
    Yeih, Weichung
    Liu, Chein-Shan
    Chang, Jiang-Ren
    ENGINEERING ANALYSIS WITH BOUNDARY ELEMENTS, 2015, 61 : 145 - 152
12345