ТОЧНЫЙ КВАДРАТИЧНЫЙ АЛГОРИТМ КРАТЧАЙШЕГО ПРЕОБРАЗОВАНИЯ ДЕРЕВЬЕВ
- Авторы: Горбунов К.Ю.1, Любецкий В.А.1,2
-
Учреждения:
- Институт проблем передачи информации им. А. А. Харкевича РАН
- Московский государственный университет им. М. В. Ломоносова
- Выпуск: Том 519, № 1 (2024)
- Страницы: 22-27
- Раздел: МАТЕМАТИКА
- URL: https://kazanmedjournal.ru/2686-9543/article/view/648010
- DOI: https://doi.org/10.31857/S2686954324050058
- EDN: https://elibrary.ru/XEFREO
- ID: 648010
Цитировать
Аннотация
В статье предложен новый точный квадратичный по сложности алгоритм, который решает задачу кратчайшего преобразования (“выравнивания”) одного нагруженного дерева в другое с учетом произвольных цен операций над деревьями. Предложен набор из трех операций: добавление вершин-делеций к ребру или корню дерева и сдвиг поддерева с делециями.
Об авторах
К. Ю. Горбунов
Институт проблем передачи информации им. А. А. Харкевича РАН
Email: gorbunov@iitp.ru
Москва, Россия
В. А. Любецкий
Институт проблем передачи информации им. А. А. Харкевича РАН; Московский государственный университет им. М. В. Ломоносова
Email: lyubetsk@iitp.ru
Москва, Россия; Москва, Россия
Список литературы
- Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология (пер. с англ.). СПб.: Невский Диалект; БХВ-Петербург, 2003, 654 с.
- Горбунов К. Ю., Любецкий В. А. Почти точный линейный алгоритм преобразования графов из цепей и циклов, с оптимизацией суммы цен операций // ДАН. 2020. Т. 494. № 1. С. 26–29. https://doi.org/10.31857/S2686954320050343
- Yuan M., Yang X., Lin J., Cao X., Chen F., Zhang X., Li Z., Zheng G., Wang X., Chen X., Yang J-R. Alignment of Cell Lineage Trees Elucidates Genetic Programs for the Development and Evolution of Cell Types // iScience. 2020. V. 23. Art. 101273. https://doi.org/10.1016/j.isci.2020.101273
- https://github.com/Chenjy0212/mdelta (Дата обращения: 20.01.2024).
- Bringmann K., Gawrychowski P., Mozes Sh., Weimann O. Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can) // ACM Trans. Algorithms. 2020. V. 16. № 4. Art. 48. https://doi.org/10.1145/3381878
Дополнительные файлы
