|
МАТЕМАТИКА
Точный квадратичный алгоритм кратчайшего преобразования деревьев
К. Ю. Горбуновa, В. А. Любецкийab a Институт проблем передачи информации им. А. А. Харкевича Российской академии наук, Москва, Россия
b Московский государственный университет имени М. В. Ломоносова, Москва, Россия
Аннотация:
В статье предложен новый точный квадратичный по сложности алгоритм, который решает задачу кратчайшего преобразования (“выравнивания”) одного нагруженного дерева в другое с учетом произвольных цен операций над деревьями. Предложен набор из трех операций: добавление вершин-делеций к ребру или корню дерева и сдвиг поддерева с делециями.
Ключевые слова:
дискретная оптимизация, кратчайшее преобразование дерева, операции над деревом, цена операции, точный алгоритм, квадратичной сложности алгоритм, выравнивание деревьев.
Образец цитирования:
К. Ю. Горбунов, В. А. Любецкий, “Точный квадратичный алгоритм кратчайшего преобразования деревьев”, Докл. РАН. Матем., информ., проц. упр., 519 (2024), 22–27
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/danma560 https://www.mathnet.ru/rus/danma/v519/p22
|
Статистика просмотров: |
Страница аннотации: | 14 |
|