Authors: Plotnikov, Roman
Erzin, Adil
Mladenović, Nenad 
Title: VNDS for the min-power symmetric connectivity problem
Journal: Optimization Letters
Volume: 13
Issue: 8
First page: 1897
Last page: 1911
Issue Date: 1-Nov-2019
Rank: M22
ISSN: 1862-4472
DOI: 10.1007/s11590-018-1324-0
We consider the NP-hard problem of synthesis of optimal spanning communication subgraph in a given arbitrary simple edge-weighted graph. This problem occurs in the wireless networks while minimizing total transmission power consumptions. We propose a new method based on the variable neighborhood decomposition search metaheuristic for the approximate solution to the problem. We have performed a numerical experiment where the proposed algorithm was executed on the randomly generated test instances. For these instances, on average, our algorithm significantly outperforms the previously known heuristics, comparing solutions obtained after the same run time. The advantage of the proposed algorithm becomes more noticeable with increasing dimensions of the problem.
Keywords: Communication network | Energy efficiency | Symmetric connectivity | Variable neighborhood decomposition search
Publisher: Springer Link
Project: Russian Foundation for Basic Research (Grants No. 16-37-60006, 16-07-00552 and 17-51-45125)
"Development of information technologies and systems for stimulation of personality?s sustainable development as one of the bases of development of digital Kazakhstan", Grant No. BR05236839

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.