[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Доклады Российской академии наук. Математика, информатика, процессы управления
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
JavaScript is disabled in your browser. Please switch it on to enable full functionality of the website
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Докл. РАН. Матем., информ., проц. упр.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Доклады Российской академии наук. Математика, информатика, процессы управления, 2024, том 519, страницы 22–27
DOI: https://doi.org/10.31857/S2686954324050058
(Mi danma560)
 

МАТЕМАТИКА

Точный квадратичный алгоритм кратчайшего преобразования деревьев

К. Ю. Горбуновa, В. А. Любецкийab

a Институт проблем передачи информации им. А. А. Харкевича Российской академии наук, Москва, Россия
b Московский государственный университет имени М. В. Ломоносова, Москва, Россия
Аннотация: В статье предложен новый точный квадратичный по сложности алгоритм, который решает задачу кратчайшего преобразования (“выравнивания”) одного нагруженного дерева в другое с учетом произвольных цен операций над деревьями. Предложен набор из трех операций: добавление вершин-делеций к ребру или корню дерева и сдвиг поддерева с делециями.
Ключевые слова: дискретная оптимизация, кратчайшее преобразование дерева, операции над деревом, цена операции, точный алгоритм, квадратичной сложности алгоритм, выравнивание деревьев.
Финансовая поддержка Номер гранта
Российский научный фонд 24-44-00099
Исследование выполнено за счёт гранта Российского научного фонда № 24-44-00099, https://rscf.ru/en/project/24-44-00099/.
Статья представлена к публикации: А. Л. Семёнов
Поступило: 24.01.2024
После доработки: 01.08.2024
Принято к публикации: 01.08.2024
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.178
Образец цитирования: К. Ю. Горбунов, В. А. Любецкий, “Точный квадратичный алгоритм кратчайшего преобразования деревьев”, Докл. РАН. Матем., информ., проц. упр., 519 (2024), 22–27
Цитирование в формате AMSBIB
\RBibitem{GorLyu24}
\by К.~Ю.~Горбунов, В.~А.~Любецкий
\paper Точный квадратичный алгоритм кратчайшего преобразования деревьев
\jour Докл. РАН. Матем., информ., проц. упр.
\yr 2024
\vol 519
\pages 22--27
\mathnet{http://mi.mathnet.ru/danma560}
\crossref{https://doi.org/10.31857/S2686954324050058}
\elib{https://elibrary.ru/item.asp?id=75994111}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/danma560
  • https://www.mathnet.ru/rus/danma/v519/p22
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Доклады Российской академии наук. Математика, информатика, процессы управления Доклады Российской академии наук. Математика, информатика, процессы управления
    Статистика просмотров:
    Страница аннотации:14