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

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

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



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






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


Дискретн. анализ и исслед. опер., 2013, том 20, номер 2, страницы 75–87 (Mi da727)  

Расширяющие операторы для задачи о независимом множестве

Д. С. Малышевab

a Нац. исслед. университет Высшая школа экономики в Ниж. Новгороде, Н. Новгород, Россия
b Нижегородский гос. университет им. Н. И. Лобачевского, Н. Новгород, Россия

Аннотация: Введено понятие расширяющего оператора для задачи о независимом множестве, являющееся полезным инструментом конструктивного формирования новых случаев эффективной разрешимости этой задачи в семействе наследственных классов графов. Данное понятие применяется к наследственным частям множества $Free(\{P_5,C_5\})$. Именно, доказано, что если для связного графа $G$ задача полиномиально разрешима в классе $Free(\{P_5,C_5,G\})$, то для любого $p$ она остаётся таковой в классе $Free(\{P_5,C_5,G\circ\overline K_2,G\oplus K_{1,p}\})$. Также найдены два новых наследственных подмножества $Free(\{P_5,C_5\})$ с полиномиально разрешимой задачей о независимом множестве, не являющиеся следствием применения указанного оператора. Библиогр. 22.

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

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

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2013, 7:3, 412–419

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

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

Образец цитирования: Д. С. Малышев, “Расширяющие операторы для задачи о независимом множестве”, Дискретн. анализ и исслед. опер., 20:2 (2013), 75–87; J. Appl. Industr. Math., 7:3 (2013), 412–419

Цитирование в формате AMSBIB
\RBibitem{Mal13}
\by Д.~С.~Малышев
\paper Расширяющие операторы для задачи о~независимом множестве
\jour Дискретн. анализ и исслед. опер.
\yr 2013
\vol 20
\issue 2
\pages 75--87
\mathnet{http://mi.mathnet.ru/da727}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3113402}
\transl
\jour J. Appl. Industr. Math.
\yr 2013
\vol 7
\issue 3
\pages 412--419
\crossref{https://doi.org/10.1134/S1990478913030149}


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

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