A Modification of the Frechet Distance for Nonnisomorphic Trees
The paper presents a modification of the Frechet distance for nonisomorphic trees. While the classical Frechet distance between nonisomorphic trees is undefined, a new measure called similarity of a tree to a reference tree is given that is defined for a wider class of trees. A polynomial time algor...
Збережено в:
| Опубліковано в: : | Control systems & computers |
|---|---|
| Дата: | 2021 |
| Автор: | |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2021
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/181259 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | A Modification of the Frechet Distance for Nonnisomorphic Trees / Ye.V. Vodolazskiy // Control systems & computers. — 2021. — № 2-3. — С. 20–27. — Бібліогр.: 8 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| Резюме: | The paper presents a modification of the Frechet distance for nonisomorphic trees. While the classical Frechet distance between nonisomorphic trees is undefined, a new measure called similarity of a tree to a reference tree is given that is defined for a wider class of trees. A polynomial time algorithm is given for determining whether similarity of one tree to another is less than a given number.
Ціль статті. Необхідно розробити метод порівняння дерев, ідеологічно близький до метрики Фреше, але виз- начений для пар неізоморфних дерев. Результати. У статті запропоновано модифікацію метрики Фреше для неізоморфних дерев. Нова числова характеристика названа близькістю дерева до еталону і визначена в тому числі для деяких класів пар неізоморфних дерев. Запропоновано поліноміальний алгоритм розпізнавання того, що одне дерево є близьким до іншого з точністю до заданого числа.
|
|---|---|
| ISBN: | DOI https://doi.org/10.15407/csc.2021.02.020 |
| ISSN: | 2706-8145 |