The Convergecast Scheduling Problem on a Regular Triangular Grid

Adil Erzin, Roman Plotnikov

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

Аннотация

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
Язык оригиналаанглийский
Название основной публикацииMathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers
РедакторыIgor Bykadorov, Vitaly Strusevich, Tatiana Tchemisova
Место публикацииCham
ИздательSpringer International Publishing AG
Страницы356-368
Число страниц13
Том1090
ISBN (печатное издание)9783030333935
DOI
СостояниеОпубликовано - 2019

Серия публикаций

НазваниеCommunications in Computer and Information Science
Том1090 CCIS
ISSN (печатное издание)1865-0929
ISSN (электронное издание)1865-0937

Fingerprint Подробные сведения о темах исследования «The Convergecast Scheduling Problem on a Regular Triangular Grid». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Erzin, A., & Plotnikov, R. (2019). The Convergecast Scheduling Problem on a Regular Triangular Grid. В I. Bykadorov, V. Strusevich, & T. Tchemisova (Ред.), Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers (Том 1090, стр. 356-368). (Communications in Computer and Information Science; Том 1090 CCIS). Springer International Publishing AG. https://doi.org/10.1007/978-3-030-33394-2_28