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

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

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



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






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


Дискретн. анализ и исслед. опер., 2017, том 24, номер 1, страницы 56–80 (Mi da863)  

$1$-Треугольные графы и совершенные окрестностные множества

П. А. Иржавский, Ю. А. Картынник, Ю. Л. Орлович

Белорусский гос. университет, пр. Независимости, 4, 220030 Минск, Беларусь

Аннотация: Граф называется $1$-треугольным, если для любого максимального независимого множества $I$ этого графа каждое ребро графа, оба конца которого не принадлежат $I$, содержится ровно в одном треугольнике с вершиной из множества $I$. Получена характеризация $1$-треугольных графов, из которой следует полиномиальный алгоритм их распознавания. Установлена сложность вычисления в классе $1$-треугольных графов ряда теоретико-графовых параметров, связанных с независимостью и доминированием. В частности, установлена $\mathrm{NP}$-полнота задачи о наименьшем совершенном окрестностном множестве в классе всех графов. Библиогр. 20.

Ключевые слова: треугольный граф, рёберно-симплициальный граф, характеризация, совершенное окрестностное множество, $\mathrm{NP}$-полнота.

Финансовая поддержка Номер гранта
Белорусский республиканский фонд фундаментальных исследований Ф15МЛД-022
Исследование выполнено частично при финансовой поддержке Белорусского республиканского фонда фундаментальных исследований (проект № Ф15МЛД–022).


DOI: https://doi.org/10.17377/daio.2017.24.532

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

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2017, 11:1, 58–69

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

Тип публикации: Статья
УДК: 519.17
Статья поступила: 16.03.2016
Переработанный вариант: 27.06.2016

Образец цитирования: П. А. Иржавский, Ю. А. Картынник, Ю. Л. Орлович, “$1$-Треугольные графы и совершенные окрестностные множества”, Дискретн. анализ и исслед. опер., 24:1 (2017), 56–80; J. Appl. Industr. Math., 11:1 (2017), 58–69

Цитирование в формате AMSBIB
\RBibitem{IrzKarOrl17}
\by П.~А.~Иржавский, Ю.~А.~Картынник, Ю.~Л.~Орлович
\paper $1$-Треугольные графы и совершенные окрестностные множества
\jour Дискретн. анализ и исслед. опер.
\yr 2017
\vol 24
\issue 1
\pages 56--80
\mathnet{http://mi.mathnet.ru/da863}
\crossref{https://doi.org/10.17377/daio.2017.24.532}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3622065}
\elib{http://elibrary.ru/item.asp?id=28905205}
\transl
\jour J. Appl. Industr. Math.
\yr 2017
\vol 11
\issue 1
\pages 58--69
\crossref{https://doi.org/10.1134/S1990478917010070}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85013919134}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da863
  • http://mi.mathnet.ru/rus/da/v24/i1/p56

    ОТПРАВИТЬ: 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
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:166
    Полный текст:38
    Литература:20
    Первая стр.:9
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020