Variable neighborhood search variants for Mm-power symmetric connectivity problem

We consider the problem of optimal communication tree construction in a given undirected weighted graph. Such a problem occurs while minimizing the power consumption of data transmission in different distributed networks in the case when network elements are able to adjust their transmission ranges....

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2017-02, Vol.78, p.557
Main Authors: Erzin, A I, Mladenovic, N, Plotnikov, R V
Format: Article
Language:English
Subjects:
Comparative analysis
Computer networks
Connectivity
Data transmission
Energy consumption
Studies
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the problem of optimal communication tree construction in a given undirected weighted graph. Such a problem occurs while minimizing the power consumption of data transmission in different distributed networks in the case when network elements are able to adjust their transmission ranges. In this paper, the most general strongly NP-hard formulation, when edge weights have arbitrary non-negative values, is considered. We propose new heuristics, mostly based on variable neighborhood search, for getting an approximate solution of the problem. Extensive comparative analysis between the proposed methods was performed. Numerical experiments demonstrated the high efficiency of the proposed heuristics.
ISSN:0305-0548
0305-0548
DOI:10.1016/j.cor.2016.05.010