Задача динамічної локалізації точки на незв'язному графі
У статті запропоновано розв'язок задачі динамічної локалізації точки на незв'язному графі за час О(logN) з використанням O(N) пам'яті. Розроблено структуру даних на основі червоно-чорного дерева, що підтримує операції вставки і вилучення ребер за час О(logN), а також введено порядок...
Збережено в:
| Опубліковано в: : | Математичні машини і системи |
|---|---|
| Дата: | 2012 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут проблем математичних машин і систем НАН України
2012
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/83775 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Задача динамічної локалізації точки на незв'язному графі / В.М. Терещенко, В.І. Пузирей // Мат. машини і системи. — 2012. — № 4. — С. 52-58. — Бібліогр.: 18 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-83775 |
|---|---|
| record_format |
dspace |
| spelling |
Терещенко, В.М. Пузирей, В.І. 2015-06-23T08:38:42Z 2015-06-23T08:38:42Z 2012 Задача динамічної локалізації точки на незв'язному графі / В.М. Терещенко, В.І. Пузирей // Мат. машини і системи. — 2012. — № 4. — С. 52-58. — Бібліогр.: 18 назв. — укр. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/83775 004.519.712 +004.92 У статті запропоновано розв'язок задачі динамічної локалізації точки на незв'язному графі за час О(logN) з використанням O(N) пам'яті. Розроблено структуру даних на основі червоно-чорного дерева, що підтримує операції вставки і вилучення ребер за час О(logN), а також введено порядок над відрізками в середині смуги і знаходження сусіднього ребра. В статье предложено решение задачи динамической локализации точки на несвязном графе за время О(logN) с использованием O(N) памяти. Разработано структуру данных на основе красно-черного дерева, которая поддерживает операции вставки и удаления ребер за время О(logN), а также введен порядок над отрезками внутри полосы и поиск соседнего ребра. In this paper we propose solving a problem of dynamic point localization on a disconnected graph during O(logN) time and using O(N) memory. The data structure of the base of red-and-black tree supporting an edge insert/delete operations using O(logN) time was developed. Segments order within a slab and finding neighbour edge clockwise was established. uk Інститут проблем математичних машин і систем НАН України Математичні машини і системи Обчислювальні системи Задача динамічної локалізації точки на незв'язному графі Задача динамической локализации точки на несвязном графе The problem of dynamic point localization on a disconnected graph Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Задача динамічної локалізації точки на незв'язному графі |
| spellingShingle |
Задача динамічної локалізації точки на незв'язному графі Терещенко, В.М. Пузирей, В.І. Обчислювальні системи |
| title_short |
Задача динамічної локалізації точки на незв'язному графі |
| title_full |
Задача динамічної локалізації точки на незв'язному графі |
| title_fullStr |
Задача динамічної локалізації точки на незв'язному графі |
| title_full_unstemmed |
Задача динамічної локалізації точки на незв'язному графі |
| title_sort |
задача динамічної локалізації точки на незв'язному графі |
| author |
Терещенко, В.М. Пузирей, В.І. |
| author_facet |
Терещенко, В.М. Пузирей, В.І. |
| topic |
Обчислювальні системи |
| topic_facet |
Обчислювальні системи |
| publishDate |
2012 |
| language |
Ukrainian |
| container_title |
Математичні машини і системи |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| format |
Article |
| title_alt |
Задача динамической локализации точки на несвязном графе The problem of dynamic point localization on a disconnected graph |
| description |
У статті запропоновано розв'язок задачі динамічної локалізації точки на незв'язному графі за час О(logN) з використанням O(N) пам'яті. Розроблено структуру даних на основі червоно-чорного дерева, що підтримує операції вставки і вилучення ребер за час О(logN), а також введено порядок над відрізками в середині смуги і знаходження сусіднього ребра.
В статье предложено решение задачи динамической локализации точки на несвязном графе за время О(logN) с использованием O(N) памяти. Разработано структуру данных на основе красно-черного дерева, которая поддерживает операции вставки и удаления ребер за время О(logN), а также введен порядок над отрезками внутри полосы и поиск соседнего ребра.
In this paper we propose solving a problem of dynamic point localization on a disconnected graph during O(logN) time and using O(N) memory. The data structure of the base of red-and-black tree supporting an edge insert/delete operations using O(logN) time was developed. Segments order within a slab and finding neighbour edge clockwise was established.
|
| issn |
1028-9763 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/83775 |
| citation_txt |
Задача динамічної локалізації точки на незв'язному графі / В.М. Терещенко, В.І. Пузирей // Мат. машини і системи. — 2012. — № 4. — С. 52-58. — Бібліогр.: 18 назв. — укр. |
| work_keys_str_mv |
AT tereŝenkovm zadačadinamíčnoílokalízacíítočkinanezvâznomugrafí AT puzireiví zadačadinamíčnoílokalízacíítočkinanezvâznomugrafí AT tereŝenkovm zadačadinamičeskoilokalizaciitočkinanesvâznomgrafe AT puzireiví zadačadinamičeskoilokalizaciitočkinanesvâznomgrafe AT tereŝenkovm theproblemofdynamicpointlocalizationonadisconnectedgraph AT puzireiví theproblemofdynamicpointlocalizationonadisconnectedgraph |
| first_indexed |
2025-12-07T17:06:23Z |
| last_indexed |
2025-12-07T17:06:23Z |
| _version_ |
1850870001724030976 |