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 252
- Downloads 0
Managing flexible care with a context aware system for ageing-in-place
This paper describes the Care4Balance (C4B) system for better facilitating communication and task coordination between formal and informal caregivers, and older adults as care receivers. Field-tests with older adults (n=...
Face recognition based on LDA in manifold subspace
Although LDA has many successes in dimensionality reduction and data separation, it also has disadvantages, especially the small sample size problem in training data because the "within-class scatter" matrix may not be a...
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...
Fast Radial and Bilateral Symmetry Detection Using Inverted Gradient Hash Maps
This paper presents a fast and novel algorithm for both radial and bilateral symmetry detection based on inverted gradient hash maps (IGHMs). A hash map is an associative array that stores image gradient magnitudes and o...
Gestures Recognition from Sound Waves
We propose a new method to recognize gestures from sound waves. The main contribution of this paper is to recognize gestures based on the analysis of short-time Fourier transforms (STFT) using the Doppler effect to sense...