Доклады Российской академии наук. Математика, информатика, процессы управления
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

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

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


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




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

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

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

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

a Институт проблем передачи информации им. А. А. Харкевича Российской академии наук, Москва, Россия
b Московский государственный университет имени М. В. Ломоносова, Москва, Россия
DOI: https://doi.org/10.31857/S2686954324050058
Аннотация: В статье предложен новый точный квадратичный по сложности алгоритм, который решает задачу кратчайшего преобразования (“выравнивания”) одного нагруженного дерева в другое с учетом произвольных цен операций над деревьями. Предложен набор из трех операций: добавление вершин-делеций к ребру или корню дерева и сдвиг поддерева с делециями.
Ключевые слова: дискретная оптимизация, кратчайшее преобразование дерева, операции над деревом, цена операции, точный алгоритм, квадратичной сложности алгоритм, выравнивание деревьев.
Финансовая поддержка Номер гранта
Российский научный фонд 24-44-00099
Исследование выполнено за счёт гранта Российского научного фонда № 24-44-00099, https://rscf.ru/en/project/24-44-00099/.
Статья представлена к публикации: А. Л. Семёнов
Поступило: 24.01.2024
После доработки: 01.08.2024
Принято к публикации: 01.08.2024
Англоязычная версия:
Doklady Mathematics, 2024, Volume 110, Issue 2, Pages 373–378
DOI: https://doi.org/10.1134/S1064562424702259
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.178
Образец цитирования: К. Ю. Горбунов, В. А. Любецкий, “Точный квадратичный алгоритм кратчайшего преобразования деревьев”, Докл. РАН. Матем., информ., проц. упр., 519 (2024), 22–27; Dokl. Math., 110:2 (2024), 373–378
Цитирование в формате 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}
\transl
\jour Dokl. Math.
\yr 2024
\vol 110
\issue 2
\pages 373--378
\crossref{https://doi.org/10.1134/S1064562424702259}
Образцы ссылок на эту страницу:
  • 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
    		Доклады Российской академии наук. Математика, информатика, процессы управления Доклады Российской академии наук. Математика, информатика, процессы управления
    Статистика просмотров:
    Страница аннотации:22
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025