Research Article
A Variable Neighborhood Search Algorithm for Solving the Steiner Minimal Tree Problem in Sparse Graphs
@ARTICLE{10.4108/eai.6-2-2019.156534, author={C. V. Tran and N. H. Ha}, title={A Variable Neighborhood Search Algorithm for Solving the Steiner Minimal Tree Problem in Sparse Graphs}, journal={EAI Endorsed Transactions on Context-aware Systems and Applications}, volume={5}, number={15}, publisher={EAI}, journal_a={CASA}, year={2018}, month={12}, keywords={Minimal tree, sparse graph, variable neighborhood search algorithm, metaheuristic algorithm, Steiner minimal tree}, doi={10.4108/eai.6-2-2019.156534} }- C. V. Tran
N. H. Ha
Year: 2018
A Variable Neighborhood Search Algorithm for Solving the Steiner Minimal Tree Problem in Sparse Graphs
CASA
EAI
DOI: 10.4108/eai.6-2-2019.156534
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.
Copyright © 2018 C.V. Tran and N. H. Ha, licensed to EAI. This is an open access article distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/3.0/), which permits unlimited use, distribution and reproduction in any medium so long as the original work is properly cited.
