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

C. Tran; N.  Ha

Research Article

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

Download905 downloads

Cite: BibTeX Plain Text

@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

C. V. Tran¹^,*, N. H. Ha²

1: The Center for Information Technology and Communication, 284 Tran Hung Dao Street, Ca Mau City, Vietnam
2: Research Institute of Posts and Telecommunications (RIPT), 122 Hoang Quoc Viet Street, Ha Noi City, Vietnam

*Contact email: chuongtv@camau.gov.vn

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.

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

Received: 2018-12-01
Accepted: 2018-12-07
Published: 2018-12-10
Publisher: EAI

: http://dx.doi.org/10.4108/eai.6-2-2019.156534

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.