Solving the Steiner tree problem in graphs by chaotic search

被引：2
作者：
Fujita, Misa [1 ]
Kimura, Takayuki [2 ]
Ikeguchi, Tohru [1 ,3 ]
机构：
[1] Tokyo Univ Sci, Grad Sch Engn, Dept Management Sci, 6-3-1 Niijuku, Tokyo 1258585, Japan
[2] Nippon Inst Technol, Fac Fundamental Engn, Dept Elect Elect & Commun Engn, 4-1 Gakuendai, Saitama 3458501, Japan
[3] Tokyo Univ Sci, Fac Engn, Dept Informat & Comp Technol, 6-3-1 Niijuku, Tokyo 1258585, Japan
来源：
IEICE NONLINEAR THEORY AND ITS APPLICATIONS | 2020年 / 11卷 / 01期
关键词：
the Steiner tree problem in graphs; combinatorial optimization; metaheuristics; the chaotic search; neural network; PACKET ROUTING-PROBLEMS; NEURODYNAMICS; ALGORITHM; STRATEGY;
D O I：
10.1587/nolta.11.90
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
The Steiner tree problem in graphs is an NP-hard combinatorial optimization problem. To solve the NP-hard combinatorial optimization problems, such as the traveling salesman problems, the quadratic assignment problems, and the vehicle routing problems, an algorithm for searching solutions by chaotic dynamics, or the chaotic search, exhibits good performance. From this viewpoint, this paper proposes an algorithm for solving the Steiner tree problem in graphs with chaotic dynamics. Comparing the performance of the chaotic search with that of the tabu search, we analyze the searching characteristics of the chaotic search. From the results of numerical experiments, we found that if parameters of the chaotic search are set to appropriate values, the chaotic search exhibits good performance and the chaotic search outputs optimal solutions more frequently than the tabu search during the searching processes, which implies that the chaotic search has higher ability than the tabu search as metaheuristics.
引用
收藏
页码：90 / 108
页数：19
相关论文
共 50 条
  • [21] Complexity of Steiner Tree in Split Graphs - Dichotomy Results
    Illuri, Madhu
    Renjith, P.
    Sadagopan, N.
    ALGORITHMS AND DISCRETE APPLIED MATHEMATICS, CALDAM 2016, 2016, 9602 : 308 - 325
  • [22] An algorithm for solving the minimum vertex ranking spanning tree problem on interval graphs
    Nakayama, SI
    Masuyama, S
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2003, E86A (05): : 1019 - 1026
  • [23] Solving the minimum labelling spanning tree problem by intelligent optimization
    Consoli, S.
    Mladenovic, N.
    Perez, J. A. Moreno
    APPLIED SOFT COMPUTING, 2015, 28 : 440 - 452
  • [24] Toward solving the Steiner travelling salesman problem on urban road maps using the branch decomposition of graphs
    Xia, Yingjie
    Zhu, Mingzhe
    Gu, Qianping
    Zhang, Luming
    Li, Xuelong
    INFORMATION SCIENCES, 2016, 374 : 164 - 178
  • [25] Solving the maximum internal spanning tree problem on interval graphs in polynomial time
    Li, Xingfu
    Feng, Haodi
    Jiang, Haotao
    Zhu, Binhai
    THEORETICAL COMPUTER SCIENCE, 2018, 734 : 32 - 37
  • [26] On the restricted k-Steiner tree problem
    Prosenjit Bose
    Anthony D’Angelo
    Stephane Durocher
    Journal of Combinatorial Optimization, 2022, 44 : 2893 - 2918
  • [27] Parameterized Approximations for the Minimum Diameter Vertex-Weighted Steiner Tree Problem in Graphs with Parameterized Weights
    Ding, Wei
    Chen, Guangting
    Qiu, Ke
    Zhou, Yu
    ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2024,
  • [28] On the restricted k-Steiner tree problem
    Bose, Prosenjit
    D'Angelo, Anthony
    Durocher, Stephane
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2022, 44 (04) : 2893 - 2918
  • [29] Some formulations for the group steiner tree problem
    Ferreira, Carlos E.
    de Oliveira Filho, Fernando M.
    DISCRETE APPLIED MATHEMATICS, 2006, 154 (13) : 1877 - 1884
  • [30] Quantum Speedup for the Minimum Steiner Tree Problem
    Miyamoto, Masayuki
    Iwamura, Masakazu
    Kise, Koichi
    Le Gall, Francois
    COMPUTING AND COMBINATORICS (COCOON 2020), 2020, 12273 : 234 - 245
12345