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

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

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



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






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


Дискретн. анализ и исслед. опер., 2016, том 23, номер 1, страницы 5–16 (Mi da835)  

Независимые множества в графах без поддеревьев с большим числом листьев

В. Е. Алексеев, Д. В. Захарова

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

Аннотация: Поддерево графа называется вписанным, если никакие три вершины этого поддерева не порождают треугольника в графе. Доказывается, что при любом фиксированном $k$ задача о независимом множестве разрешима за полиномиальное время для графов, входящих в один из следующих классов: 1) графы, не имеющие поддеревьев с $k$ листьями, 2) субкубические графы, не имеющие вписанных поддеревьев с $k$ листьями, 3) графы со степенями, не превосходящими $k$, не имеющие порождённых поддеревьев с 4 листьями. Ил. 1, библиогр. 12.

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

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


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

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

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2016, 10:1, 1–6

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

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

Образец цитирования: В. Е. Алексеев, Д. В. Захарова, “Независимые множества в графах без поддеревьев с большим числом листьев”, Дискретн. анализ и исслед. опер., 23:1 (2016), 5–16; J. Appl. Industr. Math., 10:1 (2016), 1–6

Цитирование в формате AMSBIB
\RBibitem{AleZak16}
\by В.~Е.~Алексеев, Д.~В.~Захарова
\paper Независимые множества в~графах без поддеревьев с~большим числом листьев
\jour Дискретн. анализ и исслед. опер.
\yr 2016
\vol 23
\issue 1
\pages 5--16
\mathnet{http://mi.mathnet.ru/da835}
\crossref{https://doi.org/10.17377/daio.2016.23.499}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3555672}
\elib{http://elibrary.ru/item.asp?id=25792209}
\transl
\jour J. Appl. Industr. Math.
\yr 2016
\vol 10
\issue 1
\pages 1--6
\crossref{https://doi.org/10.1134/S1990478916010014}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84961602268}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da835
  • http://mi.mathnet.ru/rus/da/v23/i1/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
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:182
    Полный текст:49
    Литература:54
    Первая стр.:34
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020