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

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

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



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






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


Модел. и анализ информ. систем, 2017, том 24, номер 2, страницы 141–154 (Mi mais554)  

Полиэдральные характеристики задач о сбалансированном и несбалансированном двудольных подграфах

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

Ярославский государственный университет им. П.Г. Демидова, ул. Советская, 14, г. Ярославль, 150003, Россия

Аннотация: Исследуются полиэдральные характеристики трех задач о построении оптимальных полных двудольных подграфов двудольных графов. В первой задаче рассматриваются сбалансированные подграфы с одинаковым числом вершин в каждой доле и произвольными весами ребер. В двух других задачах речь идет о несбалансированных подграфах максимального и минимального веса с неотрицательными ребрами. Устанавливается, что все три задачи являются NP-трудными. В работе изучаются многогранники и конусные разбиения рассматриваемых задач, а также их графы. Для задачи о сбалансированном подграфе приводится условие смежности вершин в полиэдральном графе и графе соответствующего конусного разбиения. Плотность полиэдрального графа оценивается снизу сверхполиномиальной функцией. Для задач о несбалансированных подграфах строятся сверхполиномиальные нижние оценки плотности графов неотрицательных конусных разбиений. Полученные результаты характеризуют временную трудоемкость задач в широком классе алгоритмов, использующих линейные сравнения.

Ключевые слова: полный двудольный граф, полиэдральный граф, конусное разбиение, плотность графа, NP-трудная задача.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 14-01-00333_а
Министерство образования и науки Российской Федерации МК-5400.2015.13
При частичной поддержке гранта РФФИ № 14-01-00333. При частичной поддержке инициативной НИР ВИП-004 АААА-А16-116070610022-6. При поддержке гранта Президента Российской Федерации МК-5400.2015.13.


DOI: https://doi.org/10.18255/1818-1015-2017-2-141-154

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

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

Тип публикации: Статья
УДК: 519.16+514.172.45
Поступила в редакцию: 25.08.2016

Образец цитирования: В. А. Бондаренко, А. В. Николаев, Д. А. Шовгенов, “Полиэдральные характеристики задач о сбалансированном и несбалансированном двудольных подграфах”, Модел. и анализ информ. систем, 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{http://elibrary.ru/item.asp?id=29063998}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mais554
  • http://mi.mathnet.ru/rus/mais/v24/i2/p141

    ОТПРАВИТЬ: 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
  • Моделирование и анализ информационных систем
    Просмотров:
    Эта страница:1996
    Полный текст:45
    Литература:14

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