The Convergecast Scheduling Problem on a Regular Triangular Grid

Adil Erzin; Roman Plotnikov

doi:10.1007/978-3-030-33394-2_28

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	https://doi.org/10.1007/978-3-030-33394-2_28
Состояние	Опубликовано - 2019

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

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

Доступ к документу

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

Link to publication in Scopus

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

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. редактор / Igor Bykadorov ; Vitaly Strusevich ; Tatiana Tchemisova. Том 1090 Cham : Springer International Publishing AG, 2019. стр. 356-368 (Communications in Computer and Information Science).

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

}

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, Communications in Computer and Information Science, том. 1090 CCIS, Springer International Publishing AG, Cham, стр. 356-368. https://doi.org/10.1007/978-3-030-33394-2_28

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. ред. / Igor Bykadorov; Vitaly Strusevich; Tatiana Tchemisova. Том 1090 Cham : Springer International Publishing AG, 2019. стр. 356-368 (Communications in Computer and Information Science; Том 1090 CCIS).

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

TY - GEN

T1 - The Convergecast Scheduling Problem on a Regular Triangular Grid

AU - Erzin, Adil

AU - Plotnikov, Roman

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

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

ER -

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