TY - GEN

T1 - The Convergecast Scheduling Problem on a Regular Triangular Grid

AU - Erzin, Adil

AU - Plotnikov, Roman

N1 - Funding Information: A. Erzin thanks the Russian Foundation for Basic Research, grant 19?47?540007 and the program of fundamental scientific researches of the SB RAS, project 0314?2019? 0014 (contribution: Sects. 1?3), and R. Plonikov thanks the Russian Science Foundation, grant 18?71?00084 (contribution: Sects. 4, 5), for financial support. Funding Information: A. Erzin thanks the Russian Foundation for Basic Research, grant 19–47–540007 and the program of fundamental scientific researches of the SB RAS, project 0314–2019– 0014 (contribution: Sects. 1–3), and R. Plonikov thanks the Russian Science Foundation, grant 18–71–00084 (contribution: Sects. 4, 5), for financial support.

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

KW - Conflict-free data aggregation scheduling

KW - Triangular grid

UR - http://www.scopus.com/inward/record.url?scp=85076184640&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-33394-2_28

DO - 10.1007/978-3-030-33394-2_28

M3 - Conference contribution

AN - SCOPUS:85076184640

SN - 9783030333935

VL - 1090

T3 - Communications in Computer and Information Science

SP - 356

EP - 368

BT - Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers

A2 - Bykadorov, Igor

A2 - Strusevich, Vitaly

A2 - Tchemisova, Tatiana

PB - Springer International Publishing AG

CY - Cham

T2 - 18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019

Y2 - 8 July 2019 through 12 July 2019

ER -