A Variable Neighborhood Search Algorithm for Solving the Steiner Minimal Tree Problem in Sparse Graphs
Journal Title: EAI Endorsed Transactions on Context-aware Systems and Applications - Year 2018, Vol 5, Issue 15
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
- EP ID EP45811
- DOI http://dx.doi.org/10.4108/eai.6-2-2019.156534
- Views 306
- Downloads 0
An Introduction to the Book Titled Nature of Computation and Communication
We introduce the book with the title of “Nature of Computation and Communication” edited by Prof. Phan Cong Vinh, Dr. Emil Vassev and Prof Mike Hinchey, and published by Springer in 2015 to scientists, researchers, profe...
Modeling the Connections of Dynamic Sensor Fields Based on BT-Graph
In this article, we propose a new approach to model and optimize the dynamic sensor field for both internal network connections and LEO satellite connection based on BT Graph. Due to the shift of LEO satellite’s orbit at...
AndroCon: An Android-Based Context-Aware Middleware Framework
Mobile devices have become major sources of context-aware data due to their ubiquity and sensing capabilities. However, deploying mobile devices as dynamic, unabridged context data provider either locally or remotely is...
Mobility Patterns Mining Algorithms with Fast Speed
In recent years, mobile networks and its applications are developing rapidly. Therefore, the issue to ensure quality of service (QoS) is a key issue for the service providers. The movement prediction of Mobile Users (MUs...
Book Titled Nature-Inspired Networking: Theory and Applications: An Introduction
Nature-Inspired Networking: Theory and Applications contains nine original, peer-reviewed chapters reporting on new developments of interest to the nature-inspired networking/computing communities. All chapters contain r...