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

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

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



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






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


Модел. и анализ информ. систем, 2015, том 22, номер 4, страницы 453–463 (Mi mais452)  

Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)

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

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

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

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

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

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 14-01-00333
Министерство образования и науки Российской Федерации МК-5400.2015.13


DOI: https://doi.org/10.18255/1818-1015-2015-4-453-463

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

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

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

Образец цитирования: В. А. Бондаренко, А. В. Николаев, Д. А. Шовгенов, “Полиэдральные графы задач об остовных деревьях при дополнительных ограничениях”, Модел. и анализ информ. систем, 22:4 (2015), 453–463

Цитирование в формате AMSBIB
\RBibitem{BonNikSho15}
\by В.~А.~Бондаренко, А.~В.~Николаев, Д.~А.~Шовгенов
\paper Полиэдральные графы задач об остовных деревьях при дополнительных ограничениях
\jour Модел. и анализ информ. систем
\yr 2015
\vol 22
\issue 4
\pages 453--463
\mathnet{http://mi.mathnet.ru/mais452}
\crossref{https://doi.org/10.18255/1818-1015-2015-4-453-463}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3418466}
\elib{http://elibrary.ru/item.asp?id=24273047}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mais452
  • http://mi.mathnet.ru/rus/mais/v22/i4/p453

    ОТПРАВИТЬ: 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

    Эта публикация цитируется в следующих статьяx:
    1. В. А. Бондаренко, А. В. Николаев, Д. А. Шовгенов, “Полиэдральные характеристики задач о сбалансированном и несбалансированном двудольных подграфах”, Модел. и анализ информ. систем, 24:2 (2017), 141–154  mathnet  crossref  elib
    2. В. А. Бондаренко, А. В. Николаев, “О графе многогранника пирамидальных циклов”, Дискретн. анализ и исслед. опер., 25:1 (2018), 5–24  mathnet  crossref  elib; V. A. Bondarenko, A. V. Nikolaev, “On the skeleton of the polytope of pyramidal tours”, J. Appl. Industr. Math., 12:1 (2018), 9–18  crossref
  • Моделирование и анализ информационных систем
    Просмотров:
    Эта страница:113
    Полный текст:39
    Литература:14

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