Authors: Erzin, Adil
Mladenović, Nenad 
Plotnikov, Roman
Title: Variable neighborhood search variants for Min-power symmetric connectivity problem
Journal: Computers and Operations Research
Volume: 78
First page: 557
Last page: 563
Issue Date: 1-Feb-2017
Rank: M21
ISSN: 0305-0548
DOI: 10.1016/j.cor.2016.05.010
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.
Keywords: Energy efficiency | NP-hard problem | Variable neighborhood search | Wireless sensor network
Publisher: Elsevier
Project: Russian Foundation for Basic Research (Grant no. 16-07-00552)
Ministry of Education and Science, Republic of Kazakhstan (Project no. 0115PK00546 )

Show full item record


checked on Jun 21, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.