Задача динамічної локалізації точки на незв'язному графі
Vernadsky National Library of Ukraine
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Задача динамічної локалізації точки на незв'язному графі
|
|
| Creator |
Терещенко, В.М.
Пузирей, В.І. |
|
| Subject |
Обчислювальні системи
|
|
| 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. |
|
| Date |
2015-06-23T08:38:42Z
2015-06-23T08:38:42Z 2012 |
|
| Type |
Article
|
|
| Identifier |
Задача динамічної локалізації точки на незв'язному графі / В.М. Терещенко, В.І. Пузирей // Мат. машини і системи. — 2012. — № 4. — С. 52-58. — Бібліогр.: 18 назв. — укр.
1028-9763 http://dspace.nbuv.gov.ua/handle/123456789/83775 004.519.712 +004.92 |
|
| Language |
uk
|
|
| Relation |
Математичні машини і системи
|
|
| Publisher |
Інститут проблем математичних машин і систем НАН України
|
|