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

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

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



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






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


Дискретн. анализ и исслед. опер., 2018, том 25, номер 2, страницы 5–18 (Mi da893)  

Новые случаи полиномиальной разрешимости задачи о независимом множестве для графов с запрещёнными путями

В. Е. Алексеев, С. В. Сорочан

Нижегородский гос. университет им. Н. И. Лобачевского, ИИТММ, пр. Гагарина, 23, корп. 6, 603950 Нижний Новгород, Россия

Аннотация: Задача о независимом множестве разрешима за полиномиальное время для графов, не содержащих пути $P_k$ при любом фиксированном $k$. Если же запрещается порождённый путь $P_k$, то при $k>6$ сложностной статус этой задачи неизвестен. Рассматриваются промежуточные случаи, когда запрещён порождённый путь $P_k$ и некоторые его остовные надграфы. Доказывается полиномиальная разрешимость задачи о независимом множестве в следующих случаях: 1) запрещаются надграфы, у которых минимальная степень вершины меньше $k/2$; 2) запрещаются надграфы, у которых дополнительный граф имеет более $k/2$ рёбер; 3) запрещаются надграфы, из которых с помощью операции пересечения графов можно получить $P_k$. Библиогр. 12.

Ключевые слова: независимое множество, запрещённый подграф, путь, надграф, полиномиальное время.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 17-01-00710a
Исследование выполнено при финансовой поддержке Российского фонда фундаментальных исследований (проект 17-01-00710a).


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

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

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2018, 12:2, 213–219

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

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

Образец цитирования: В. Е. Алексеев, С. В. Сорочан, “Новые случаи полиномиальной разрешимости задачи о независимом множестве для графов с запрещёнными путями”, Дискретн. анализ и исслед. опер., 25:2 (2018), 5–18; J. Appl. Industr. Math., 12:2 (2018), 213–219

Цитирование в формате AMSBIB
\RBibitem{AleSor18}
\by В.~Е.~Алексеев, С.~В.~Сорочан
\paper Новые случаи полиномиальной разрешимости задачи о~независимом множестве для графов с~запрещёнными путями
\jour Дискретн. анализ и исслед. опер.
\yr 2018
\vol 25
\issue 2
\pages 5--18
\mathnet{http://mi.mathnet.ru/da893}
\crossref{https://doi.org/10.17377/daio.2018.25.581}
\elib{http://elibrary.ru/item.asp?id=32729776}
\transl
\jour J. Appl. Industr. Math.
\yr 2018
\vol 12
\issue 2
\pages 213--219
\crossref{https://doi.org/10.1134/S1990478918020023}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85047800693}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da893
  • http://mi.mathnet.ru/rus/da/v25/i2/p5

    ОТПРАВИТЬ: 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
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:80
    Полный текст:5
    Литература:10
    Первая стр.:2

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