Constructive Heuristics for Min-Power Bounded-Hops Symmetric Connectivity Problem

Roman Plotnikov, Adil Erzin

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

1 Citation (Scopus)

Abstract

We consider a problem of constructing an energy-efficient bounded diameter communication spanning tree when the vertices are located on a plane, and the energy required to transmit a message between a pair of vertices is proportional to the squared distance between them. For this NP-hard problem, we have developed several approximate heuristic algorithms. The results of a posteriori analysis of solutions constructed by the proposed algorithms are presented.

Original languageEnglish
Title of host publicationMathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers
EditorsIgor Bykadorov, Vitaly Strusevich, Tatiana Tchemisova
Place of PublicationCham
PublisherSpringer International Publishing AG
Pages390-407
Number of pages18
Volume1090
ISBN (Print)9783030333935, 978-3-030-33394-2
DOIs
Publication statusPublished - 2019
Event18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019 - Ekaterinburg, Russian Federation
Duration: 8 Jul 201912 Jul 2019

Publication series

NameCommunications in Computer and Information Science
Volume1090 CCIS
ISSN (Print)1865-0929
ISSN (Electronic)1865-0937

Conference

Conference18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019
CountryRussian Federation
CityEkaterinburg
Period08.07.201912.07.2019

Keywords

  • Approximation algorithms
  • Bounded hops
  • Energy efficiency
  • Symmetric connectivity

Fingerprint

Dive into the research topics of 'Constructive Heuristics for Min-Power Bounded-Hops Symmetric Connectivity Problem'. Together they form a unique fingerprint.

Cite this