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

A 802.22b protocol for inter/intra WRAN communication

In this paper we focus on cognitive 802.22b Wireless Regional Area Networks (WRANs). In particular a protocol, named inter intra-resource sharing algorithm (2I-RSA), is presented to address the problem of self coexistenc...

Bootstrapped Discovery and Ranking of Relevant Services and Information in Context-aware Systems

A context-aware system uses context to provide relevant information and services to the user, where relevancy depends on the user’s situation. This relevant information could include a wide range of heterogeneous content...

A federation of simulations based on cellular automata in cyber-physical systems

In cyber-physical system (CPS), cooperation between a variety of computational and physical elements usually poses difficulties to current modelling and simulation tools. Although much research has proposed to address th...

Document Level Sentiment Analysis: A survey

Sentiment analysis becomes a very active research area in the text mining field. It aims to extract people's opinions, sentiments, and subjectivity from the texts. Sentiment analysis can be performed at three levels: at...

Exploiting Nonnegative Matrix Factorization with Mixed Group Sparsity Constraint to Separate Speech Signal from Single-channel Mixture with Unknown Ambient Noise

This paper focuses on solving a challenging speech enhancement problem: improving the desired speech from a single-channel audio signal containing high-level unspecified noise (possibly environmental noise, music, other...