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

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

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



Информ. и её примен.:
Год:
Том:
Выпуск:
Страница:
Найти






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


Информ. и её примен., 2017, том 11, выпуск 1, страницы 79–89 (Mi ia461)  

Алгоритм преобразования одного графа в другой с минимальной ценой

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

a Институт проблем передачи информации им. А. А. Харкевича Российской академии наук
b Механико-математический факультет Московского государственного университета им. М. В. Ломоносова

Аннотация: Рассматриваются ориентированные графы, состоящие из любого числа дизъюнктных цепей и циклов, ребрам графов приписаны без повторений их имена — натуральные числа. Фиксирован список операций, каждая из которых по-своему преобразует один граф в другой, ей приписано число — цена данной операции. Нужно найти минимальную по суммарной цене последовательность операций, которая для двух данных графов преобразует один в другой. Эта задача самым широким образом применяется в прикладных вопросах. По-видимому, она является NP-трудной и поэтому может быть эффективно решена только при том или ином условии на цены или при некотором ограничении на графы. Ее решение при достаточно широких условиях получено в виде линейных по времени и памяти алгоритмов, для которых доказана точность (неэвристичность), т. е. доказано, что они всегда находят минимальную по цене последовательность операций. Задача давно решается многими эвристическими алгоритмами, которые тестировались на разных данных, но предлагаемые авторами решения — первые среди точных.

Ключевые слова: ориентированный граф из цепей и циклов; преобразование графов с минимальной ценой; точное линейное решение; условие на графы; условие на цены; условно кратчайшее решение.

Финансовая поддержка Номер гранта
Российский научный фонд 14-50-00150
Работа выполнена при финансовой поддержке Российского научного фонда (проект 14-50-00150).


DOI: https://doi.org/10.14357/19922264170107

Полный текст: PDF файл (259 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья
Поступила в редакцию: 26.04.2016

Образец цитирования: К. Ю. Горбунов, В. А. Любецкий, “Алгоритм преобразования одного графа в другой с минимальной ценой”, Информ. и её примен., 11:1 (2017), 79–89

Цитирование в формате AMSBIB
\RBibitem{GorLyu17}
\by К.~Ю.~Горбунов, В.~А.~Любецкий
\paper Алгоритм преобразования одного графа в другой с минимальной ценой
\jour Информ. и её примен.
\yr 2017
\vol 11
\issue 1
\pages 79--89
\mathnet{http://mi.mathnet.ru/ia461}
\crossref{https://doi.org/10.14357/19922264170107}
\elib{http://elibrary.ru/item.asp?id=29159457}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/ia461
  • http://mi.mathnet.ru/rus/ia/v11/i1/p79

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Информатика и её применения
    Просмотров:
    Эта страница:129
    Полный текст:29
    Литература:8
    Первая стр.:2

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019