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

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

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


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




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

Дискретная математика, 2017, том 29, выпуск 3, страницы 114–125
DOI: https://doi.org/10.4213/dm1440 (Mi dm1440) 		 
Эта публикация цитируется в 1 научной статье (всего в 1 статье)

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

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

Национальный исследовательский университет «Высшая школа экономики», Нижегородский государственный университет им. Н. И. Лобачевского
PDF полного текста (506 kB) Список цитирования (1)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.4213/dm1440
Аннотация: Задача о независимом множестве для заданного обыкновенного графа состоит в вычислении размера наибольшего множества его попарно несмежных вершин. Предлагается новый способ редукции графов. С его помощью получено новое доказательство NP-полноты задачи о независимом множестве в классе планарных графов и доказана NP-полнота данной задачи в классе плоских графов, имеющих только треугольные внутренние грани, с максимальной степенью вершин 18.
Ключевые слова: независимые множества, планарный граф, планарная триангуляция, вычислительная сложность.
Финансовая поддержка Номер гранта
Российский научный фонд 17-11-01336
Исследование выполнено за счет гранта Российского научного фонда (проект № 17-11-01336).
Статья поступила: 16.12.2016
Англоязычная версия:
Discrete Mathematics and Applications, 2018, Volume 28, Issue 4, Pages 249–258
DOI: https://doi.org/10.1515/dma-2018-0022
Реферативные базы данных:
УДК: 519.17
Образец цитирования: Д. В. Сироткин, Д. С. Малышев, “Способ редукции графов и его приложения”, Дискрет. матем., 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{https://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{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000442245400004}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85053113965}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/dm1440
  • https://doi.org/10.4213/dm1440
  • https://www.mathnet.ru/rus/dm/v29/i3/p114
    • Эта публикация цитируется в следующих 1 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Дискретная математика
    Статистика просмотров:
    Страница аннотации:483
    PDF полного текста:85
    Список литературы:53
    Первая страница:28
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024