ТОЧНЫЙ КВАДРАТИЧНЫЙ АЛГОРИТМ КРАТЧАЙШЕГО ПРЕОБРАЗОВАНИЯ ДЕРЕВЬЕВ

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Доступ платный или только для подписчиков

Аннотация

В статье предложен новый точный квадратичный по сложности алгоритм, который решает задачу кратчайшего преобразования (“выравнивания”) одного нагруженного дерева в другое с учетом произвольных цен операций над деревьями. Предложен набор из трех операций: добавление вершин-делеций к ребру или корню дерева и сдвиг поддерева с делециями.

Об авторах

К. Ю. Горбунов

Институт проблем передачи информации им. А. А. Харкевича РАН

Email: gorbunov@iitp.ru
Москва, Россия

В. А. Любецкий

Институт проблем передачи информации им. А. А. Харкевича РАН; Московский государственный университет им. М. В. Ломоносова

Email: lyubetsk@iitp.ru
Москва, Россия; Москва, Россия

Список литературы

  1. Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология (пер. с англ.). СПб.: Невский Диалект; БХВ-Петербург, 2003, 654 с.
  2. Горбунов К. Ю., Любецкий В. А. Почти точный линейный алгоритм преобразования графов из цепей и циклов, с оптимизацией суммы цен операций // ДАН. 2020. Т. 494. № 1. С. 26–29. https://doi.org/10.31857/S2686954320050343
  3. 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
  4. https://github.com/Chenjy0212/mdelta (Дата обращения: 20.01.2024).
  5. 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

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2024