Authors: Plotnikov, Roman
Erzin, Adil
Mladenović, Nenad 
Title: Approximation algorithms for the min-power symmetric connectivity problem
Journal: AIP Conference Proceedings
Volume: 1776
Issue Date: 20-Oct-2016
ISBN: 978-0-735-41438-9
ISSN: 0094-243X
DOI: 10.1063/1.4965333
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 the total transmission power consumptions. We propose several new heuristics based on the variable neighborhood search metaheuristic for the approximation solution of the problem.We have performed a numerical experiment where all proposed algorithms have been executed on the randomly generated test samples. For these instances, on average, our algorithms outperform the previously known heuristics.
Publisher: American Institute of Physics
Project: Russian Foundation for Basic Research (grant no. 16-37- 60006)
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

Page view(s)

checked on May 9, 2024

Google ScholarTM




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