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

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

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


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




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

Доклады Российской академии наук. Математика, информатика, процессы управления, 2020, том 494, страницы 26–29
DOI: https://doi.org/10.31857/S2686954320050343 (Mi danma111) 		 
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)

МАТЕМАТИКА

Почти точный линейный алгоритм преобразования графов из цепей и циклов, с оптимизацией суммы цен операций

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

a Институт проблем передачи информации им. А.А. Харкевича Российской академии наук, Москва, Россия
b Московский государственный университет имени М. В. Ломоносова, Москва, Россия
PDF полного текста (99 kB) Список цитирования (2)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.31857/S2686954320050343
Аннотация: Построен алгоритм преобразования одного графа в другой для нагруженных ориентированных графов, составленных из цепей и циклов. Алгоритм работает линейное время и выдает последовательность преобразований с наименьшим, с точностью до аддитивной ошибки, суммарным весом, причем цены операций вставки и удаления участка ребер могут быть различными и отличаться от цены остальных операций. Аддитивная ошибка оценена через веса операций.
Ключевые слова: точный алгоритм, преобразование графов, граф степени 2, граф из цепей и циклов, цена операции, DCJ-операции, дискретная оптимизация.
Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 18–29–13037
Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта 18–29–13037.
Статья представлена к публикации: А. Л. Семёнов
Поступило: 17.05.2020
После доработки: 20.08.2020
Принято к публикации: 28.08.2020
Англоязычная версия:
Doklady Mathematics, 2020, Volume 102, Issue 2, Pages 376–379
DOI: https://doi.org/10.1134/S1064562420050324
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.178
Образец цитирования: К. Ю. Горбунов, В. А. Любецкий, “Почти точный линейный алгоритм преобразования графов из цепей и циклов, с оптимизацией суммы цен операций”, Докл. РАН. Матем., информ., проц. упр., 494 (2020), 26–29; Dokl. Math., 102:2 (2020), 376–379
Цитирование в формате AMSBIB
\RBibitem{GorLyu20}
\by К.~Ю.~Горбунов, В.~А.~Любецкий
\paper Почти точный линейный алгоритм преобразования графов из цепей и циклов, с оптимизацией суммы цен операций
\jour Докл. РАН. Матем., информ., проц. упр.
\yr 2020
\vol 494
\pages 26--29
\mathnet{http://mi.mathnet.ru/danma111}
\crossref{https://doi.org/10.31857/S2686954320050343}
\elib{https://elibrary.ru/item.asp?id=44344642}
\transl
\jour Dokl. Math.
\yr 2020
\vol 102
\issue 2
\pages 376--379
\crossref{https://doi.org/10.1134/S1064562420050324}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/danma111
  • https://www.mathnet.ru/rus/danma/v494/p26
    • Эта публикация цитируется в следующих 2 статьяx:
    1. K. Yu. Gorbunov, V. A. Lyubetsky, “An Exact Quadratic Algorithm for the Shortest Tree Transformation”, Dokl. Math., 2024  crossref
    2. К. Ю. Горбунов, В. А. Любецкий, “Точный квадратичный алгоритм кратчайшего преобразования деревьев”, Докл. РАН. Матем., информ., проц. упр., 519 (2024), 22–27  mathnet  crossref [K. Yu. Gorbunov, V. A. Lyubetskii, “An exact quadratic algorithm for the shortest tree transformation”, Dokl. RAN. Math. Inf. Proc. Upr., 519 (2024), 22–27  mathnet]
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Доклады Российской академии наук. Математика, информатика, процессы управления Доклады Российской академии наук. Математика, информатика, процессы управления
    Статистика просмотров:
    Страница аннотации:120
    PDF полного текста:31
    Список литературы:29
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025