• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • Национальный исследовательский университет «Высшая школа экономики»
  • Публикации ВШЭ
  • Статьи
  • A method of graph reduction and its applications
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Приоритетные направления
  • бизнес-информатика
  • государственное и муниципальное управление
  • гуманитарные науки
  • инженерные науки
  • компьютерно-математическое
  • математика
  • менеджмент
  • право
  • социология
  • экономика
по году
  • 2028
  • 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
  • еще
Тематика
Новости
18 сентября 2026 г.
«Время на содержательные вопросы у нас не лимитировалось»
Международная лаборатория атомистического суперкомпьютерного моделирования и многомасштабного анализа НИУ ВШЭ провела масштабную конференцию «Молекулярная динамика». Участники могли услышать всех докладчиков, а сами докладчики — ответить на любое количество содержательных вопросов. О подготовке конференции и дискуссиях «Вышка.Главное» поговорила с заведующим лабораторией Григорием Смирновым и ее главным научным сотрудником Генри Норманом.
18 сентября 2026 г.
Ученые ВШЭ займутся изучением очарованных адронов в рамках BESIII
Высшая школа экономики стала университетом — участником международной коллаборации BESIII (Beijing Spectrometer III) в области физики высоких энергий. Присоединение к коллаборации стало первым практическим результатом реализации меморандума о сотрудничестве, подписанного в 2025 году между НИУ ВШЭ и Институтом физики высоких энергий (IHEP) в Пекине (КНР).
17 сентября 2026 г.
<a>НИУ ВШЭ представил в Китае исследование о безопасности нейросетей для анализа видео
Ученые Высшей школы экономики презентавали на международной конференции ChinaMM 2026 в Китае исследование о том, как искажения при передаче видео влияют на работу нейросетей. Авторы предложили новый способ проверять устойчивость таких моделей в условиях, близких к реальному использованию видеосервисов.

 

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

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

?

A method of graph reduction and its applications

Discrete Mathematics and Applications. 2018. Vol. 28. No. 4. P. 249–258.
Сироткин Д. В., Малышев Д. С.

The independent set problem for a given simple graph is to determine the size of a maximal set
of its pairwise non-adjacent vertices. We propose a new way of graph reduction leading to a new proof of
the NP-completeness of the independent set problem in the class of planar graphs and to the proof of NPcompleteness of this problem in the class of planar graphs having only triangular internal facets of maximal
vertex degree 18

Научное направление: Математика Компьютерные науки
Приоритетные направления: компьютерно-математическое математика
Язык: английский
Полный текст
DOI
Ключевые слова: planar graph independent setsComputational Complexityplanar triangulation
Похожие публикации
Обобщение пространства Фока
Дильмухаметова Алия Мидхатовна, Напалков В. В., Муллабаева А. У., Уфимский математический журнал 2010 Т. 2 № 1 С. 52–58
В данной статье введены обобщённые пространства Фока и рассмотрены основные свойства этих пространств. Найдена операция, сопряженная к операции умножения на переменную в обобщенном пространстве Фока. Также определены собственные функции сопряженного оператора. Изучены обобщенное преобразование Лапласа и задача построения базиса для введенных пространств. ...
Добавлено: 21 сентября 2026 г.
Segmentation of the Iris and Pupil of the Human Eye in Images from an Infrared Camera
Aleksei Samarin, Alexander Savelev, Aleksei Toropov и др., Pattern Recognition and Image Analysis 2024 Vol. 34 No. 3 P. 855–862
Добавлено: 21 сентября 2026 г.
A Model Based on Universal Filters for Image Color Correction
Aleksei Samarin, Назаренко А. А., Alexander Savelev и др., Pattern Recognition and Image Analysis 2024 Vol. 34 No. 3 P. 844–854
Добавлено: 21 сентября 2026 г.
Streptococci Recognition in Microscope Images Using Taxonomy-based Visual Features
Aleksei Samarin, Alexander Savelev, Aleksei Toropov и др., Optical Memory and Neural Networks (Information Optics) 2024 Vol. 33 P. 424–434
Добавлено: 21 сентября 2026 г.
Specialized Image Descriptors Adaptation for Polyp Recognition over Endoscopic Images
Aleksei Samarin, Aleksei Toropov, Alexander Savelev и др., Pattern Recognition and Image Analysis 2024 Vol. 34 No. 4 P. 1053–1060
Добавлено: 21 сентября 2026 г.
Lightweight Image Preprocessing Model for Improving Microorganism Detection in Microscopic Scenes
Самарин А. В., Торопов А. Г., Савельев А. Г. и др., Pattern Recognition and Image Analysis 2024 Vol. 34 No. 4 P. 1044–1052
Добавлено: 21 сентября 2026 г.
Advancements in Signal, Image and Video Processing
Singapore: Springer Singapore, 2025.
Добавлено: 21 сентября 2026 г.
Interpretable Lazy Classification with Interval Pattern Structures and Local Interval Explanations
Томат А., Sergei O. Kuznetsov, International Journal of Approximate Reasoning 2026 Vol. 197 Article 109754
Добавлено: 21 сентября 2026 г.
IDAP++: Advancing Divergence-Based Pruning via Filter-Level and Layer-Level Optimization
Aleksei Samarin, Назаренко А. А., Kotenko E. и др., / Series arXiv "math". 2025. No. 2511.20141.
Добавлено: 21 сентября 2026 г.
Об одном классе дифференциальных уравнений с переменными коэффициентами
Дильмухаметова Алия Мидхатовна, Напалков В. В., «Doklady Mathematics» 2009 Т. 424 № 5 С. 591–593
В данной статье вводится определенный класс дифференциальных уравнений с переменными коэффициентами, который тесно связан с операцией умножения Адамара и операторами Данкла имеющими применение в математической физике. Показано, что уравнения этого класса могут быть сведены к уранвениям в обобщенных производных с постоянными коэффициентами. ...
Добавлено: 21 сентября 2026 г.
Modernized Nonlocal Blocks for Infrared Camera Image Segmentation of the Human Eye
Aleksei Samarin, Alexander Savelev, Aleksei Toropov и др., Pattern Recognition and Image Analysis 2025 Vol. 35 No. 2 P. 169–178
Добавлено: 21 сентября 2026 г.
Non-Contrast Brain CT Images Segmentation Enhancement: Lightweight Pre-Processing Model for Ultra-Early Ischemic Lesion Recognition and Segmentation
Aleksei Samarin, Alexander Savelev, Aleksei Toropov и др., Journal of Imaging 2025 Vol. 11 No. 10 Article 359
Добавлено: 21 сентября 2026 г.
ФУНДАМЕНТАЛЬНЫЙ ПРИНЦИП ЭЙЛЕРА ДЛЯ ОДНОГО КЛАССА ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ В ЧАСТНЫХ ПРОИЗВОДНЫХ С ПЕРЕМЕННЫМИ КОЭФФИЦИЕНТАМИ
Дильмухаметова Алия Мидхатовна, Напалков В. В., «Doklady Mathematics» 2012 Т. 443 № 3 С. 293–295
В данной работе введены обобщенные частные производные, изучены дифференциальные уравнения в обобщенных частных производных с постоянными коэффициентами и доказан фундаментальный принцип Эйлера для таких уравнений. Устанавливлена связь с классом уравнений в обычных частных производных с переменными коэффициентами. ...
Добавлено: 21 сентября 2026 г.
Pattern Recognition. ICPR 2024 International Workshops and Challenges
Springer, Cham, 2025.
Добавлено: 21 сентября 2026 г.
Vague stimulating ideas, images and metaphors in scientific thinking: researchers' work with horizons of unclear knowledge
Поддьяков А. Н., / Series Social Science Research Network "Social Science Research Network". 2026. No. 7437658.
Добавлено: 15 сентября 2026 г.
On phase-lock area parquet in a special slow-fast limit of model of Josephson junction.
Глуцюк А. А., / Series arXiv "math". 2026.
Добавлено: 8 сентября 2026 г.
Infinitely many graph manifolds with unique geometrical piece that admit arbitrarily many Anosov flows
Починка О. В., Шмуклер В. И., / Series math.RT "arXiv:1808.06395 [math.RT]". 2026.
Добавлено: 31 августа 2026 г.
On calibration of remote sensing retrievals of ecosystem respiration (Reco) with tower measurements over,Russian forests and wetlands
Shabanov N., Kuricheva O., Kurbatova J. и др., / Series Working Papers SSRN "Department of Economics Ca’ Foscari University of Venice". 2026.
Добавлено: 21 августа 2026 г.
Three Algorithms for Merging Hierarchical Navigable Small World Graphs
Пономаренко А. А., / Series Computer Science "arxiv.org". 2025.
Добавлено: 30 июля 2026 г.
New bound on S1× S2-setting Bell locality of a nonseparable Werner state
Лубенец Е. Р., / Series arxiv.org "quant-ph". 2026. No. 2607.18050.
Добавлено: 21 июля 2026 г.
On functional equations for Chow polylogarithms
Болбачан В. С., / Series math "arxiv.org". 2024.
Полилогарифмы Чжоу — это специальные функции, возникающие при явном описании отображения регулятора Бейлинсона. Наиболее интересное функциональное уравнение для этой функции отражает тот факт, что она обращается в нуль на границе в комплексе циклов Блоха. Мы показываем, что это функциональное уравнение формально вытекает из более простых свойств: кососимметричности, функториальности и мультипликативности. Для доказательства этого мы рассматриваем ...
Добавлено: 16 июля 2026 г.
On Goncharov’s conjecture in next to Milnor degree
Болбачан В. С., / Series math "arxiv.org". 2024.
Пусть K поле характеристики ноль. Мы доказываем что его когомологии в степени m-1 и весе m рационально изоморфны когомологиям полилогарифмического комплекса в соответствующей степени. Это дает частичное расширение теоремы Суслина, описывающую неразложимую K теорию K_3 для поля. ...
Добавлено: 16 июля 2026 г.
Statistical inference based on band-limited kernels: Rational-infinitely divisible distributions and beyond
Панов В. А., Рябченко А. П., / Series arXiv "stat.ME". 2026. No. 2607.05048.
Добавлено: 9 июля 2026 г.
Growth in noncommutative algebras and entropy in derived categories
Пионтковский Д. И., / Series arXiv "math". 2026.
Добавлено: 23 июня 2026 г.
  • О ВЫШКЕ
  • Цифры и факты
  • Руководство и структура
  • Устойчивое развитие в НИУ ВШЭ
  • Преподаватели и сотрудники
  • Корпуса и общежития
  • Закупки
  • Обращения граждан в НИУ ВШЭ
  • Фонд целевого капитала
  • Противодействие коррупции
  • Сведения о доходах, расходах, об имуществе и обязательствах имущественного характера
  • Сведения об образовательной организации
  • Людям с ограниченными возможностями здоровья
  • Единая платежная страница
  • Работа в Вышке
  • ОБРАЗОВАНИЕ
  • Лицей
  • Довузовская подготовка
  • Олимпиады
  • Прием в бакалавриат
  • Вышка+
  • Прием в магистратуру
  • Аспирантура
  • Дополнительное образование
  • Центр развития карьеры
  • Бизнес-инкубатор ВШЭ
  • Образовательные партнерства
  • Обратная связь и взаимодействие с получателями услуг
  • НАУКА
  • Научные подразделения
  • Исследовательские проекты
  • Мониторинги
  • Диссертационные советы
  • Защиты диссертаций
  • Академическое развитие
  • Конкурсы и гранты
  • Внешние научно-информационные ресурсы
  • РЕСУРСЫ
  • Библиотека
  • Издательский дом ВШЭ
  • Книжный магазин «БукВышка»
  • Типография
  • Медиацентр
  • Журналы ВШЭ
  • Публикации
  • http://www.minobrnauki.gov.ru/
    Министерство науки и высшего образования РФ
  • https://edu.gov.ru/
    Министерство просвещения РФ
  • https://elearning.hse.ru/mooc
    Массовые открытые онлайн-курсы
  • НИУ ВШЭ1993–2026
  • Адреса и контакты
  • Условия использования материалов
  • Политика обработки персональных данных
  • Правила применения рекомендательных технологий в НИУ ВШЭ
  • Карта сайта
Редактору