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 301
- Downloads 0
Maintenance process control: cellular automata approach
In this work we consider an industrial maintenance process control problem using cellular automata approach. The problem consists on finding an optimal control for the assignment and the displacement of agents in a spati...
Visible Position Estimation in Whole Wrist Circumference Device towards Forearm Pose-aware Display
Smart watches allow instant access to information; however, the visual notification is not always reachable depending on the forearm posture. Flexible and curved display technologies can enable full-wrist circumference di...
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...
Hybrid Algorithms of Whale optimization algorithm and k-nearest neighbor to Predict the liver disease
Liver Disease is one of the most common diseases which can be prevented by early diagnosis and up-todate treatment. Advances in machine learning and intelligence techniques have led to the effective diagnosis and predicti...
Querying Object-Oriented Databases Based on Signature Graph and n-ary Tree
In this paper, we suggest a new technique to create index helping for querying almost identical similarities with keywords in case there is no correct match found. It’s based on a signature graph and n-ary tree helping t...