The Convergecast Scheduling Problem on a Regular Triangular Grid

Adil Erzin, Roman Plotnikov

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

Abstract

The problem of conflict-free data aggregation in an arbitrary graph is NP-hard. On a square unit grid, in each node of which a sensor is located, the problem is polynomially solvable. For the case when the graph is a regular triangular grid, the upper bound on the length of the schedule of conflict-free data aggregation was previously known. In this paper, the refined estimates are given for the length of the schedule of conflict-free data aggregation on a triangular grid, as well as polynomially solvable cases are found and algorithms for constructing optimal and approximate schedules are proposed.

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
Pages356-368
Number of pages13
Volume1090
ISBN (Print)9783030333935
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

  • Conflict-free data aggregation scheduling
  • Triangular grid

Fingerprint Dive into the research topics of 'The Convergecast Scheduling Problem on a Regular Triangular Grid'. Together they form a unique fingerprint.

Cite this