Standard
The Convergecast Scheduling Problem on a Regular Triangular Grid. / Erzin, Adil; Plotnikov, Roman.
Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers. ed. / Igor Bykadorov; Vitaly Strusevich; Tatiana Tchemisova. Vol. 1090 Cham : Springer International Publishing AG, 2019. p. 356-368 (Communications in Computer and Information Science; Vol. 1090 CCIS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Erzin, A & Plotnikov, R 2019,
The Convergecast Scheduling Problem on a Regular Triangular Grid. in I Bykadorov, V Strusevich & T Tchemisova (eds),
Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers. vol. 1090, Communications in Computer and Information Science, vol. 1090 CCIS, Springer International Publishing AG, Cham, pp. 356-368, 18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019, Ekaterinburg, Russian Federation,
08.07.2019.
https://doi.org/10.1007/978-3-030-33394-2_28
APA
Vancouver
Erzin A, Plotnikov R.
The Convergecast Scheduling Problem on a Regular Triangular Grid. In Bykadorov I, Strusevich V, Tchemisova T, editors, Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers. Vol. 1090. Cham: Springer International Publishing AG. 2019. p. 356-368. (Communications in Computer and Information Science). doi: 10.1007/978-3-030-33394-2_28
Author
Erzin, Adil ; Plotnikov, Roman. /
The Convergecast Scheduling Problem on a Regular Triangular Grid. Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers. editor / Igor Bykadorov ; Vitaly Strusevich ; Tatiana Tchemisova. Vol. 1090 Cham : Springer International Publishing AG, 2019. pp. 356-368 (Communications in Computer and Information Science).
BibTeX
@inproceedings{fe3b43633cb847949ff4cf99d64553b3,
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",
note = "Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG.; 18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019 ; Conference date: 08-07-2019 Through 12-07-2019",
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",
}
RIS
TY - GEN
T1 - The Convergecast Scheduling Problem on a Regular Triangular Grid
AU - Erzin, Adil
AU - Plotnikov, Roman
N1 - Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
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 -