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

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

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


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




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

Моделирование и анализ информационных систем, 2017, том 24, номер 2, страницы 141–154
DOI: https://doi.org/10.18255/1818-1015-2017-2-141-154 (Mi mais554) 		 
Полиэдральные характеристики задач о сбалансированном и несбалансированном двудольных подграфах

В. А. Бондаренко, А. В. Николаев, Д. А. Шовгенов

Ярославский государственный университет им. П.Г. Демидова, ул. Советская, 14, г. Ярославль, 150003, Россия
PDF полного текста (549 kB)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.18255/1818-1015-2017-2-141-154
Аннотация: Исследуются полиэдральные характеристики трех задач о построении оптимальных полных двудольных подграфов двудольных графов. В первой задаче рассматриваются сбалансированные подграфы с одинаковым числом вершин в каждой доле и произвольными весами ребер. В двух других задачах речь идет о несбалансированных подграфах максимального и минимального веса с неотрицательными ребрами. Устанавливается, что все три задачи являются NP-трудными. В работе изучаются многогранники и конусные разбиения рассматриваемых задач, а также их графы. Для задачи о сбалансированном подграфе приводится условие смежности вершин в полиэдральном графе и графе соответствующего конусного разбиения. Плотность полиэдрального графа оценивается снизу сверхполиномиальной функцией. Для задач о несбалансированных подграфах строятся сверхполиномиальные нижние оценки плотности графов неотрицательных конусных разбиений. Полученные результаты характеризуют временную трудоемкость задач в широком классе алгоритмов, использующих линейные сравнения.
Ключевые слова: полный двудольный граф, полиэдральный граф, конусное разбиение, плотность графа, NP-трудная задача.
Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 14-01-00333_а
Министерство образования и науки Российской Федерации МК-5400.2015.13
При частичной поддержке гранта РФФИ № 14-01-00333. При частичной поддержке инициативной НИР ВИП-004 АААА-А16-116070610022-6. При поддержке гранта Президента Российской Федерации МК-5400.2015.13.
Поступила в редакцию: 25.08.2016
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.16+514.172.45
Образец цитирования: В. А. Бондаренко, А. В. Николаев, Д. А. Шовгенов, “Полиэдральные характеристики задач о сбалансированном и несбалансированном двудольных подграфах”, Модел. и анализ информ. систем, 24:2 (2017), 141–154
Цитирование в формате AMSBIB
\RBibitem{BonNikSho17}
\by В.~А.~Бондаренко, А.~В.~Николаев, Д.~А.~Шовгенов
\paper Полиэдральные характеристики задач о~сбалансированном и несбалансированном двудольных подграфах
\jour Модел. и анализ информ. систем
\yr 2017
\vol 24
\issue 2
\pages 141--154
\mathnet{http://mi.mathnet.ru/mais554}
\crossref{https://doi.org/10.18255/1818-1015-2017-2-141-154}
\elib{https://elibrary.ru/item.asp?id=29063998}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/mais554
  • https://www.mathnet.ru/rus/mais/v24/i2/p141
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Моделирование и анализ информационных систем
    Статистика просмотров:
    Страница аннотации:2155
    PDF полного текста:134
    Список литературы:42
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024