A Variable Neighborhood Search Algorithm for Solving the Steiner Minimal Tree Problem in Sparse Graphs

C. V. Tran; N. H. Ha

doi:10.4108/eai.6-2-2019.156534

A Variable Neighborhood Search Algorithm for Solving the Steiner Minimal Tree Problem in Sparse Graphs

Authors

C. V. Tran Center for Information Technology and Communication,
N. H. Ha Research Institute of Posts and Telecommunications

DOI:

https://doi.org/10.4108/eai.6-2-2019.156534

Keywords:

Minimal tree, sparse graph, variable neighborhood search algorithm, metaheuristic algorithm, Steiner minimal tree

Abstract

Steiner Minimal Tree (SMT) is a complex optimization problem that has many important applications in science and technology; This is a NP-hard problem. Much research has been carried out to solve the SMT problem using approximate algorithms. This paper presents A Variable Neighborhood Search (VNS) algorithm for solving the SMT problem in sparse graphs; The proposed algorithm has been tested on sparse graphs in a standardized experimental data system, and it yields better results than some other heuristic algorithms.

Downloads

Published

10-12-2018

How to Cite

Tran CV, Ha NH. A Variable Neighborhood Search Algorithm for Solving the Steiner Minimal Tree Problem in Sparse Graphs. EAI Endorsed Trans Context Aware Syst App [Internet]. 2018 Dec. 10 [cited 2024 Dec. 27];5(15):e4. Available from: https://publications.eai.eu/index.php/casa/article/view/1944

Download Citation

Issue

Vol. 5 No. 15 (2018): EAI Endorsed Transactions on Context-aware Systems and Applications

Section

Research article

License

This work is licensed under a Creative Commons Attribution 3.0 Unported License.

This is an open-access article distributed under the terms of the Creative Commons Attribution CC BY 3.0 license, which permits unlimited use, distribution, and reproduction in any medium so long as the original work is properly cited.