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 [J].

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 [J].

Nakayama, SI ;

Masuyama, S .

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2003, E86A (05) :1019-1026

[23] Solving the maximum internal spanning tree problem on interval graphs in polynomial time [J].

Li, Xingfu ;

Feng, Haodi ;

Jiang, Haotao ;

Zhu, Binhai .

THEORETICAL COMPUTER SCIENCE, 2018, 734 :32-37

[24] Solving the minimum labelling spanning tree problem by intelligent optimization [J].

Consoli, S. ;

Mladenovic, N. ;

Perez, J. A. Moreno .

APPLIED SOFT COMPUTING, 2015, 28 :440-452

[25] Toward solving the Steiner travelling salesman problem on urban road maps using the branch decomposition of graphs [J].

Xia, Yingjie ;

Zhu, Mingzhe ;

Gu, Qianping ;

Zhang, Luming ;

Li, Xuelong .

INFORMATION SCIENCES, 2016, 374 :164-178

[26] Some formulations for the group steiner tree problem [J].

Ferreira, Carlos E. ;

de Oliveira Filho, Fernando M. .

DISCRETE APPLIED MATHEMATICS, 2006, 154 (13) :1877-1884

[27] Quantum Speedup for the Minimum Steiner Tree Problem [J].

Miyamoto, Masayuki ;

Iwamura, Masakazu ;

Kise, Koichi ;

Le Gall, Francois .

COMPUTING AND COMBINATORICS (COCOON 2020), 2020, 12273 :234-245

[28] Parameterized Approximations for the Minimum Diameter Vertex-Weighted Steiner Tree Problem in Graphs with Parameterized Weights [J].

Ding, Wei ;

Chen, Guangting ;

Qiu, Ke ;

Zhou, Yu .

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2025, 42 (04)

[29] On the restricted k-Steiner tree problem [J].

Bose, Prosenjit ;

D'Angelo, Anthony ;

Durocher, Stephane .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2022, 44 (04) :2893-2918

[30] On the restricted k-Steiner tree problem [J].

Prosenjit Bose ;

Anthony D’Angelo ;

Stephane Durocher .

Journal of Combinatorial Optimization, 2022, 44 :2893-2918

← 1 2 3 4 5 →