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

Tran Chuong; Ha Nam

Context-Aware Systems and Applications, and Nature of Computation and Communication. 7th EAI International Conference, ICCASA 2018, and 4th EAI International Conference, ICTCC 2018, Viet Tri City, Vietnam, November 22–23, 2018, Proceedings

Research Article

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

Download

217 downloads

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.1007/978-3-030-06152-4_19,
    author={Tran Chuong and Ha Nam},
    title={A Variable Neighborhood Search Algorithm for Solving the Steiner Minimal Tree Problem},
    proceedings={Context-Aware Systems and Applications, and Nature of Computation and Communication. 7th EAI International Conference, ICCASA 2018, and 4th EAI International Conference, ICTCC 2018, Viet Tri City, Vietnam, November 22--23, 2018, Proceedings},
    proceedings_a={ICCASA \& ICTCC},
    year={2019},
    month={1},
    keywords={Minimal tree Sparse graph Variable neighborhood search algorithm Metaheuristic algorithm Steiner minimal tree},
    doi={10.1007/978-3-030-06152-4_19}
}

Tran Chuong
Ha Nam
Year: 2019
A Variable Neighborhood Search Algorithm for Solving the Steiner Minimal Tree Problem
ICCASA & ICTCC
Springer
DOI: 10.1007/978-3-030-06152-4_19

Tran Chuong¹^,*, Ha Nam²^,*

1: The Center for Information Technology and Communication
2: Research Institute of Posts and Telecommunications (RIPT)

*Contact email: chuongtv@camau.gov.vn, namhh@ptit.edu.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; 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

Published: 2019-01-04
Appears in: SpringerLink

: http://dx.doi.org/10.1007/978-3-030-06152-4_19