casa 18(15): e4

Research Article

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

Download84 downloads
  • @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. Tran1,*, N. H. Ha2
  • 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.