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

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.

Authors and Affiliations

C. V. Tran, N. H. Ha

Keywords

Related Articles

On Sustaining Dynamic Adaptation of Context-Aware Services

The modern human is getting more and more mobile having access to online services by using mobile cutting-edge computational devices. In the last decade, the field of context-aware services had led to emerge several work...

Quality of Context in Context-Aware Systems

Context-aware Systems (CASs) are becoming increasingly popular and can be found in the areas of wearable computing, mobile computing, robotics, adaptive and intelligent user interfaces. Sensors are the corner stone of co...

A Context-dependent Service Model

In service-oriented systems a service invariably is bound to a contract. This contract includes the functionalities and quality of services guarantees that the provider can make. But such guarantees are not absolute. A s...

8th EAI International Conference on Context-Aware Systems and Applications (ICCASA 2019) AND 5th EAI International Conference on Nature of Computation and Communication (ICTCC 2019)

The ICCASA and ICTCC 2019 conferences sponsored by EAI, Tien Giang University (TGU) and Nguyen Tat Thanh University (NTTU) are place for highly original ideas about how context-awareness and nature are going to shape net...

Human Object Detection based on Context Awareness in the Surroundings

Surveillance system has been applied in providing public security for many complex places like railway stations, bus stops, etc. In most cases, human object detection is an important task in surveillance system. In the c...

Download PDF file
  • EP ID EP45811
  • DOI http://dx.doi.org/10.4108/eai.6-2-2019.156534
  • Views 303
  • Downloads 0

How To Cite

C. V. Tran, N. H. Ha (2018). A Variable Neighborhood Search Algorithm for Solving the Steiner Minimal Tree Problem in Sparse Graphs. EAI Endorsed Transactions on Context-aware Systems and Applications, 5(15), -. https://europub.co.uk/articles/-A-45811