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

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

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


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




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

Доклады Российской академии наук. Математика, информатика, процессы управления, 2020, том 494, страницы 26–29
DOI: https://doi.org/10.31857/S2686954320050343 (Mi danma111) 		 
МАТЕМАТИКА

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

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

a Институт проблем передачи информации им. А.А. Харкевича Российской академии наук, Москва, Россия
b Московский государственный университет имени М. В. Ломоносова, Москва, Россия
PDF полного текста (99 kB)
Список литературы:
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
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Доклады Российской академии наук. Математика, информатика, процессы управления Доклады Российской академии наук. Математика, информатика, процессы управления
    Статистика просмотров:
    Страница аннотации:67
    PDF полного текста:18
    Список литературы:7
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024