VNDS for the min-power symmetric connectivity problem

Roman Plotnikov, Adil Erzin, Nenad Mladenovic

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование

3 Цитирования (Scopus)


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.

Язык оригиналаанглийский
Страницы (с-по)1897-1911
Число страниц15
ЖурналOptimization Letters
Номер выпуска8
СостояниеОпубликовано - 1 ноя 2019


Подробные сведения о темах исследования «VNDS for the min-power symmetric connectivity problem». Вместе они формируют уникальный семантический отпечаток (fingerprint).