• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • Национальный исследовательский университет «Высшая школа экономики»
  • Публикации ВШЭ
  • Статьи
  • Способ редукции графов и его приложения
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Приоритетные направления
  • бизнес-информатика
  • государственное и муниципальное управление
  • гуманитарные науки
  • инженерные науки
  • компьютерно-математическое
  • математика
  • менеджмент
  • право
  • социология
  • экономика
по году
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • еще
Тематика
Новости
24 июня 2026 г.
Древняя чашекрания - новый вид брахиопод с необычной формой раковины и образом жизни
Российские ученые из Высшей школы экономики, МГУ имени М.В. Ломоносова и Таллинского технического университета изучили ископаемый вид древних брахиопод (плеченогих), который обитал в теплом море на севере современной Эстонии более 445 миллионов лет назад. Древняя брахиопода росла в форме чашки со «шляпкой», чтобы защититься от зарастания. Исследование опубликовано в журнале Palaeogeography, Palaeoclimatology, Palaeoecology.
23 июня 2026 г.
<a><a><a>НИУ ВШЭ и Positive Technologies наградили проекты молодых ученых по оценке последствий кибератак
Молодые исследователи из ведущих вузов страны представили проекты по прогнозированию и оценке последствий кибератак. Защита идей прошла 22 июня в Москве в рамках междисциплинарного научного конкурса, организованного Институтом мировой военной экономики и стратегии НИУ ВШЭ и Positive Technologies. Победителями стали команды Военно-космической академии имени Можайского, НИУ ВШЭ и университета «Сириус» — они разделят грантовый фонд в три миллиона рублей и продолжат свои разработки под руководством научных наставников.
23 июня 2026 г.
Дрожь земли: ученые ВШЭ научились отслеживать опасные подземные вибрации в реальном времени
Исследователи из МИЭМ ВШЭ и ИПКОН РАН разработали новую математическую модель мониторинга, которая позволяет фиксировать источник опасных подземных вибраций в реальном времени. Технология поможет снизить риск повреждения зданий, дорог и другой инфраструктуры рядом с карьерами и шахтами. Работа ученых опубликована в журнале «Горная промышленность».

 

Нашли опечатку?
Выделите её, нажмите Ctrl+Enter и отправьте нам уведомление. Спасибо за участие!

Публикации
  • Книги
  • Статьи
  • Главы в книгах
  • Препринты
  • Верификация публикаций
  • Расширенный поиск
  • Правила использования материалов
  • Наука в ВШЭ

?

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

Дискретная математика. 2017. Т. 29. № 3. С. 114–125.
Сироткин Д. В., Малышев Д. С.

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

Научное направление: Компьютерные науки Математика
Приоритетные направления: компьютерно-математическое математика
Язык: русский
Полный текст
DOI
Ключевые слова: вычислительная сложностьнезависимое множествопланарный графплоская триангуляция
Похожие публикации
On Projective Threefolds with Two-Dimensional Space of Vanishing Cycles
Fedorov Timofey, Moscow Mathematical Journal 2026 Vol. 26 No. 1 P. 73–85
Добавлено: 25 июня 2026 г.
Современные методы теории краевых задач. Понтрягинские чтения XXXVII.
Воронеж: Издательский дом ВГУ, 2026.
В сборнике представлены материалы докладов и лекций, включенных в программу весенней математической школы. ...
Добавлено: 25 июня 2026 г.
Воронежская зимняя матаматическая школа С. Г. Крейна - 2026.
Воронеж: Издательский дом ВГУ, 2026.
В сборнике представлены материалы докладов и лекций,  включенных в программу Воронежской зимней матаматической школы С. Г. Крейна - 2026. ...
Добавлено: 25 июня 2026 г.
Моделирование полностью роботизированного склада со стеллажами глубокого хранения
Гаджимирзаев Ш. М., Хельвас А. В., Computer Research and Modeling 2026 Vol. 18 No. 2 P. 423–438
В данной статье рассматривается модель полностью роботизированного склада с глубо кими стеллажами, предназначенного для хранения коробочных товаров. Основное внимание уделено оптимизации работы склада за счет дискретного мультиагентного моделирования дви жения шаттлов, выполняющих задачи по отгрузке и размещению коробок. Авторы исследуют различные стратегии размещения товаров в зонах склада, включая алгоритмы NCPA (Nearest Channel Positioning Algorithm), MECGP (Most Empty Channel Group Placement) ...
Добавлено: 24 июня 2026 г.
A machine learning dataset on winter roads of Krasnoyarsk Krai, Russia for the forestry and infrastructural projects
Подольская Е. С., Sinitsina A., European Journal of Forest Engineering 2026 Vol. 12 No. 1 P. 7–21
Добавлено: 24 июня 2026 г.
Нахождение формальных степенно–логарифмических разложений решений 𝑞–разностных уравнений
Гаянов Н. В., Парусникова А. В., Уфимский математический журнал 2026 Т. 18 № 2 С. 14–22
Рассматривается алгебраическое 𝑞-разностное уравнение. Предлагается достаточное условие существования формального степенно–логарифмического разложения решения такого уравнения в окрестности нуля. Приводится пример применения этого достаточного условия для построения формального разложения решения некоторого 𝑞-разностного аналога пятого уравнения Пенлеве при конкретных значениях параметров уравнения; рассматриваются два различных значения числа 𝑞, приводящие к качественно разным формальным асимптотическим разложениям решений. ...
Добавлено: 24 июня 2026 г.
Open r-spin theory II: The analogue of Witten's conjecture for r-spin disks
Буряк А. Ю., Clader E., Tessler R., Journal of Differential Geometry 2024 Vol. 128 No. 1 P. 1–75
Добавлено: 23 июня 2026 г.
Tautological relations and integrable systems
Буряк А. Ю., Shadrin S., Epijournal de Geometrie Algebrique 2024 Vol. 8
Добавлено: 23 июня 2026 г.
Counting meromorphic differentials on $CP^1$
Буряк А. Ю., Rossi P., Letters in Mathematical Physics 2024 Vol. 114 Article 97
Добавлено: 23 июня 2026 г.
Moduli spaces of residueless meromorphic differentials and the KP hierarchy
Буряк А. Ю., Rossi P., Zvonkine D., Geometry and Topology 2024 Vol. 28 P. 2793–2824
We prove that the cohomology classes of the moduli spaces of residueless meromorphic differentials, ie the closures, in the moduli space of stable curves, of the loci of smooth curves whose marked points are the zeros and poles of prescribed orders of a meromorphic differential with vanishing residues, form a partial cohomological field theory (CohFT) of ...
Добавлено: 23 июня 2026 г.
DR-иерархии: от пространств модулей кривых к интегрируемым системам
Буряк А. Ю., Труды Математического института им. В.А. Стеклова РАН 2024 Т. 325 С. 26–66
Основная цель работы -- показать, что DR-иерархии, введенные автором в более ранней работе, позволяют наиболее ясно установить связь между топологией компактификации Делиня-Мамфорда пространства модулей гладких алгебраических кривых рода g с n отмеченными точками и интегрируемыми системами математической физики. Также обсуждается перспективный подход, даваемый теорией DR-иерархий, к решению общей проблемы в области гипотез виттеновского типа, а именно к доказательству существования иерархии Дубровина-Чжана ...
Добавлено: 23 июня 2026 г.
Growth in noncommutative algebras and entropy in derived categories
Пионтковский Д. И., / Series arXiv "math". 2026.
Добавлено: 23 июня 2026 г.
Multilinear nilalgebras and the Jacobian theorem
Пионтковский Д. И., / Series arXiv "math". 2025.
Добавлено: 23 июня 2026 г.
The state and prospects of using virtual reality technologies in sports: a brief review
Atlasov B., Сельский А. К., Russian Journal of Information Technology in Sports 2025 Vol. 2 No. 1 P. 13–21
В статье рассматривается текущее состояние глобального рынка технологий виртуальной и дополненной реальности (VR/AR) в спорте, отмечается его рост, хотя и более медленный, чем ожидалось ранее. Особое внимание уделено российскому рынку, где развитие VR-технологий в спорте отстает от мировых лидеров, таких как США, страны ЕС и Китай, но при этом имеет значительный потенциал для роста. Проведен ...
Добавлено: 23 июня 2026 г.
2025 9th International Conference on Information, Control, and Communication Technologies (ICCT-2025)
IEEE, 2026.
Добавлено: 23 июня 2026 г.
Proceedings of the 4th Workshop on NLP for Music and Audio (NLP4MusA 2026)
Бузаев Ф. А., Mullakhmetov R., Bogachev R. и др., Association for Computational Linguistics, 2026.
Добавлено: 22 июня 2026 г.
Zα and Zβ Localize ADAR1 to Flipons That Modulate Innate Immunity, Alternative Splicing, and Nonsynonymous RNA Editing
Herbert A., Cherednichenko O., Lybrand T. и др., International Journal of Molecular Sciences 2025 Vol. 26 No. 6 Article 2422
Добавлено: 22 июня 2026 г.
Международная конференция «Математические идеи академика П.Л. Чебышёва, их приложения в естественных науках и технологи- ях искусственного интеллекта», приуроченная к 205-й годовщине со дня его рождения» : Материалы конференции. / (Обнинск, 14–16 мая 2026 г.): Материалы конференции. Под ред. акад. В.Б. Бетелина. — Калуга: Калужский печатный двор, 2026. — 232 с.
Калужский печатный двор, 2026.
Сборник трудов конференции "Математические идеи академика П.Л. Чебышёва, их приложения в естественных науках и технологиях искусственного интеллекта» ...
Добавлено: 20 июня 2026 г.
Strong Approximations for Markov Chains Weakly Converging to Diffusions
Конаков В. Д., Кучер Д. А., Mammen E., / Series arXiv "math". 2026. No. 2606.11142v1.
Добавлено: 11 июня 2026 г.
Universal Comparison Methodology for Hough Transform Approaches
Kazimirov D., Vitalii Gulevskii, Kroshnin A. и др., Mathematics 2026 Article 1136
Добавлено: 28 мая 2026 г.
ML-based Fast Simulation of FARICH Responses
Шипилов Ф. А., Barnyakov A., Ivanov A. и др., / Series Physics "arxiv.org". 2026.
Добавлено: 19 мая 2026 г.
Bifurcations and Structural Stability of Generic PC-HC Families
Доровский А. А., / Series arXiv "math". 2026.
Добавлено: 14 мая 2026 г.
On the minimum number of maximal distance-k independent sets in trees
Талецкий Д. С., / Series arXiv "math". 2026.
Добавлено: 1 мая 2026 г.
On Arithmetic Mirror Symmetry for smooth Fano fourfolds
Овчаренко М. А., / Series arXiv "math". 2026.
Добавлено: 30 апреля 2026 г.
  • О ВЫШКЕ
  • Цифры и факты
  • Руководство и структура
  • Устойчивое развитие в НИУ ВШЭ
  • Преподаватели и сотрудники
  • Корпуса и общежития
  • Закупки
  • Обращения граждан в НИУ ВШЭ
  • Фонд целевого капитала
  • Противодействие коррупции
  • Сведения о доходах, расходах, об имуществе и обязательствах имущественного характера
  • Сведения об образовательной организации
  • Людям с ограниченными возможностями здоровья
  • Единая платежная страница
  • Работа в Вышке
  • ОБРАЗОВАНИЕ
  • Лицей
  • Довузовская подготовка
  • Олимпиады
  • Прием в бакалавриат
  • Вышка+
  • Прием в магистратуру
  • Аспирантура
  • Дополнительное образование
  • Центр развития карьеры
  • Бизнес-инкубатор ВШЭ
  • Образовательные партнерства
  • Обратная связь и взаимодействие с получателями услуг
  • НАУКА
  • Научные подразделения
  • Исследовательские проекты
  • Мониторинги
  • Диссертационные советы
  • Защиты диссертаций
  • Академическое развитие
  • Конкурсы и гранты
  • Внешние научно-информационные ресурсы
  • РЕСУРСЫ
  • Библиотека
  • Издательский дом ВШЭ
  • Книжный магазин «БукВышка»
  • Типография
  • Медиацентр
  • Журналы ВШЭ
  • Публикации
  • http://www.minobrnauki.gov.ru/
    Министерство науки и высшего образования РФ
  • https://edu.gov.ru/
    Министерство просвещения РФ
  • http://www.edu.ru
    Федеральный портал «Российское образование»
  • https://elearning.hse.ru/mooc
    Массовые открытые онлайн-курсы
  • НИУ ВШЭ1993–2026
  • Адреса и контакты
  • Условия использования материалов
  • Политика конфиденциальности
  • Правила применения рекомендательных технологий в НИУ ВШЭ
  • Карта сайта
Редактору