Задача динамічної локалізації точки на незв'язному графі

• Published in: Математичні машини і системи
• Date: 2012
• Main Authors: Терещенко, В.М., Пузирей, В.І.
• Format: Article
• Language: Ukrainian
• Published: Інститут проблем математичних машин і систем НАН України 2012
• Subjects: Обчислювальні системи
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/83775
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Задача динамічної локалізації точки на незв'язному графі / В.М. Терещенко, В.І. Пузирей // Мат. машини і системи. — 2012. — № 4. — С. 52-58. — Бібліогр.: 18 назв. — укр.

У статті запропоновано розв'язок задачі динамічної локалізації точки на незв'язному графі за час О(logN) з використанням O(N) пам'яті. Розроблено структуру даних на основі червоно-чорного дерева, що підтримує операції вставки і вилучення ребер за час О(logN), а також введено порядок...