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

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

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


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




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

Дискретный анализ и исследование операций, 2017, том 24, выпуск 1, страницы 56–80
DOI: https://doi.org/10.17377/daio.2017.24.532 (Mi da863) 		 
$1$-Треугольные графы и совершенные окрестностные множества

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

Белорусский гос. университет, пр. Независимости, 4, 220030 Минск, Беларусь
PDF полного текста (393 kB)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.17377/daio.2017.24.532
Аннотация: Граф называется $1$-треугольным, если для любого максимального независимого множества $I$ этого графа каждое ребро графа, оба конца которого не принадлежат $I$, содержится ровно в одном треугольнике с вершиной из множества $I$. Получена характеризация $1$-треугольных графов, из которой следует полиномиальный алгоритм их распознавания. Установлена сложность вычисления в классе $1$-треугольных графов ряда теоретико-графовых параметров, связанных с независимостью и доминированием. В частности, установлена $\mathrm{NP}$-полнота задачи о наименьшем совершенном окрестностном множестве в классе всех графов. Библиогр. 20.
Ключевые слова: треугольный граф, рёберно-симплициальный граф, характеризация, совершенное окрестностное множество, $\mathrm{NP}$-полнота.
Финансовая поддержка Номер гранта
Белорусский республиканский фонд фундаментальных исследований Ф15МЛД-022
Исследование выполнено частично при финансовой поддержке Белорусского республиканского фонда фундаментальных исследований (проект № Ф15МЛД–022).
Статья поступила: 16.03.2016
Переработанный вариант: 27.06.2016
Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2017, Volume 11, Issue 1, Pages 58–69
DOI: https://doi.org/10.1134/S1990478917010070
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.17
Образец цитирования: П. А. Иржавский, Ю. А. Картынник, Ю. Л. Орлович, “$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://mathscinet.ams.org/mathscinet-getitem?mr=3622065}
\elib{https://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{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85013919134}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/da863
  • https://www.mathnet.ru/rus/da/v24/i1/p56
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Дискретный анализ и исследование операций
    Статистика просмотров:
    Страница аннотации:284
    PDF полного текста:186
    Список литературы:42
    Первая страница:9
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024