|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||Abstract:||
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
checked on Sep 26, 2021
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.