@inproceedings{ce8b051ccba64e27b2e39424536d0006,
title = "The Convergecast Scheduling Problem on a Regular Triangular Grid",
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",
keywords = "Conflict-free data aggregation scheduling, Triangular grid",
author = "Adil Erzin and Roman Plotnikov",
year = "2019",
doi = "10.1007/978-3-030-33394-2_28",
language = "English",
isbn = "9783030333935",
volume = "1090",
series = "Communications in Computer and Information Science",
publisher = "Springer International Publishing AG",
pages = "356--368",
editor = "Igor Bykadorov and Vitaly Strusevich and Tatiana Tchemisova",
booktitle = "Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers",
address = "Switzerland",
}