@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",

}