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

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

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



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






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


Дискрет. матем., 2017, том 29, выпуск 3, страницы 114–125 (Mi dm1440)  

Способ редукции графов и его приложения

Д. В. Сироткин, Д. С. Малышев

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

Аннотация: Задача о независимом множестве для заданного обыкновенного графа состоит в вычислении размера наибольшего множества его попарно несмежных вершин. Предлагается новый способ редукции графов. С его помощью получено новое доказательство NP-полноты задачи о независимом множестве в классе планарных графов и доказана NP-полнота данной задачи в классе плоских графов, имеющих только треугольные внутренние грани, с максимальной степенью вершин 18.

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

Финансовая поддержка Номер гранта
Российский научный фонд 17-11-01336
Исследование выполнено за счет гранта Российского научного фонда (проект № 17-11-01336).


DOI: https://doi.org/10.4213/dm1440

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

Англоязычная версия:
Discrete Mathematics and Applications, 2018, 28:4, 249–258

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

УДК: 519.17
Статья поступила: 16.12.2016

Образец цитирования: Д. В. Сироткин, Д. С. Малышев, “Способ редукции графов и его приложения”, Дискрет. матем., 29:3 (2017), 114–125; Discrete Math. Appl., 28:4 (2018), 249–258

Цитирование в формате AMSBIB
\RBibitem{SirMal17}
\by Д.~В.~Сироткин, Д.~С.~Малышев
\paper Способ редукции графов и его приложения
\jour Дискрет. матем.
\yr 2017
\vol 29
\issue 3
\pages 114--125
\mathnet{http://mi.mathnet.ru/dm1440}
\crossref{https://doi.org/10.4213/dm1440}
\elib{http://elibrary.ru/item.asp?id=29887805}
\transl
\jour Discrete Math. Appl.
\yr 2018
\vol 28
\issue 4
\pages 249--258
\crossref{https://doi.org/10.1515/dma-2018-0022}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000442245400004}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85053113965}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/dm1440
  • https://doi.org/10.4213/dm1440
  • http://mi.mathnet.ru/rus/dm/v29/i3/p114

    ОТПРАВИТЬ: 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
  • Дискретная математика
    Просмотров:
    Эта страница:160
    Литература:9
    Первая стр.:22

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