• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • Национальный исследовательский университет «Высшая школа экономики»
  • Публикации ВШЭ
  • Статьи
  • An intractability result for the vertex 3-colourability problem
  • 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
  • еще
Тематика
Новости
23 сентября 2026 г.
<a>В НИУ ВШЭ испытали робота с ИИ для распознавания окружающей среды
Инженеры и исследователи Института робототехнических систем НИУ ВШЭ провели первые испытания нейросетевой модели для распознавания среды непосредственно на роботе-собаке. Робот передвигался по зданию НИУ ВШЭ на Покровке, а также по Покровскому бульвару, анализируя окружающую обстановку и определяя, в какой сцене и локации он находится.
21 сентября 2026 г.
Ученые НИУ ВШЭ показали, что врожденные нарушения моторики влияют на развитие мозга
Исследователи из Института когнитивных нейронаук НИУ ВШЭ обобщили результаты своих предыдущих исследований, посвященных особенностям развития мозга у детей с акушерским параличом плечевого сплетения и артрогрипозом. Анализ показал, что нарушение моторики в раннем возрасте не только ведет к недостатку двигательного опыта, но и влияет на память, категориальное мышление и обработку информации. Работа опубликована в журнале Frontiers in Psychology.
22 сентября 2026 г.
Как россияне взаимодействуют с ИИ при поиске информации в интернете
Школа коммуникаций НИУ ВШЭ и Online Market Intelligence провели исследование пользовательского поискового опыта в российском сегменте интернета. Как показали результаты, пользователи в России уже воспринимают ИИ-ответ в выдаче как естественную часть поиска и используют его наравне с привычным списком ссылок. При этом на рынке самостоятельных нейросетей (отдельных чат‑ботов) уверенно лидирует Алиса AI от Яндекса  —  ее регулярно используют 40 % опрошенных.

 

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

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

?

An intractability result for the vertex 3-colourability problem

Optimization Letters. 2022. Vol. 16. P. 1403–1409.
Malyshev D. S., Приставченко О. В.
Научное направление: Математика Компьютерные науки
Язык: английский
Полный текст
DOI
Текст на другом сайте
Ключевые слова: Computational Complexityhereditary graph classvertex 3-colourability
ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:
Современные подходы к анализу сетевых структур (2022)
Похожие публикации
Анализ протокола выработки общего ключа для управления микросхемой интеллектуальной карты
Добрина Д. Н., Нестеренко А. Ю., Прикладная дискретная математика. Приложение 2026 № 19 С. 151–159
Работа содержит результаты формального анализа криптографических механизмов, входящих в состав проекта методических рекомендаций «Защищенный универсальный протокол передачи данных и управления микросхемой интеллектуальной карты» (протокол SECUNDA). Получена формальная модель и перечень трудноразрешимых математических задач, трудоёмкостью решения которых можно оценить стойкость используемых криптографических механизмов. ...
Добавлено: 24 сентября 2026 г.
Pairings on the algebra of Laurent series over a ring
Левашев В. А., / Series arXiv "math". 2026. No. 2609.06010.
Добавлено: 24 сентября 2026 г.
Discovering object-centric Petri nets with parametric arcs
I.I. Sergeev, I.A. Lomazova, Modeling and Analysis of Information Systems 2026 Vol. 33 No. 3 P. 394–419
Объектно-ориентированный process mining сформировался как эффективная парадигма анализа событийных данных, включающих несколько взаимодействующих бизнес-объектов. Существующие методы обнаружения моделей часто опираются на объектно-ориентированные сети Петри с фиксированными кратностями дуг, что ограничивает их способность представлять параметрические закономерности потребления и производства ресурсов, а также отражать количественные зависимости между взаимодействующими типами объектов. В данной работе предлагается метод обнаружения объектно-ориентированных ...
Добавлено: 24 сентября 2026 г.
Vector systems of Painlevé type
Соколов В. В., Adler V. E., Journal of Geometry and Physics 2026 Vol. 227 Article 105860
Добавлено: 24 сентября 2026 г.
ON VECTOR SCHWARZ — KdV EQUATION
Соколов В. В., BALAKHNEV M. Y., Ufa Mathematical Journal 2026 Vol. 18 No. №3 P. 85–93
Добавлено: 24 сентября 2026 г.
Lorentzian Principal Bundles with Compact Structure Groups and Causal Properties
Яковлев Е. И., Maksimov D. A., Mathematical notes 2026 Vol. 120 No. 3 P. 483–496
Исследуются гладкие главные расслоения, тотальные пространства и базы которых представляют собой ориентированные во времени лоренцевы многообразия, а проекции являются лоренцевыми субмерсиями, сохраняющими ориентации во времени. Ранее авторами было показано, что хронологичность, причинность и устойчивая причинность всегда поднимаются с базы на пространство лоренцева расслоения, для сильной причинности и глобальной гиперболичности это верно в случае компактности структурной группы. В данной ...
Добавлено: 24 сентября 2026 г.
Novikov equations for commuting differential operators of orders 3,4,5
Соколов В. В., Shabat G. B., Tsiganov A. V., Journal of Geometry and Physics 2026 Vol. 220
Добавлено: 24 сентября 2026 г.
Hadrons in N=2 supersymmetric QCD from non-Abelian string on 2D black hole
Маршаков А. В., Yung A., Ievlev E. и др., Physical Review D - Particles, Fields, Gravitation and Cosmology 2026 No. 114 P. 1–22
Добавлено: 24 сентября 2026 г.
From non-polynomial invariants to non-Liouvillian first integrals
Demina M.V., Нечитайло В. Г., Analysis and Mathematical Physics 2026 Vol. 16 No. 5 P. 1–25
We present a method of finding non-Liouvillian first integrals of rational two-dimensional differential systems. The method is based on the existence of two independent invariants that satisfy a linear second-order ordinary differential equation with respect to one of the variables. We call systems with this property R-integrable. These invariants are not necessarily polynomial; they can ...
Добавлено: 24 сентября 2026 г.
An Asymptotic Version of the Parametrix Method for Markov Chains Converging to Diffusions
Bitter I., Конаков В. Д., Mathematical notes 2026 Vol. 120 No. 4 P. 599–615
Добавлено: 24 сентября 2026 г.
Iterative construction of the R-matrices in arbitrary dimensions
Пятов П. Н., Пивоваров П. А., / Series math "arxiv.org". 2026. No. 2609.06274.
Добавлено: 24 сентября 2026 г.
Hybrid Graph Retrieval-Augmented Language Agents for Collaborative Recommendation
Ivan Bulychev, Савченко А. В., AI 2026 Vol. 7 No. 9 Article 380
Добавлено: 24 сентября 2026 г.
Risks and the image of the future in the study of AI technologies prospects
Снегирев А. Ю., Сычев С. В., Futures 2026 Vol. 183 P. 1–22
Добавлено: 23 сентября 2026 г.
Choosing Between AI Responses: How Valence, Arousal, and Dominance Shape User Preference
Паршаков П. А., Паклина С. Н., International Journal of Human-Computer Interaction 2026 P. 1–17
Добавлено: 23 сентября 2026 г.
A Two-Stage Deep Reinforcement Learning Framework for Radio Resource Management and Network Slicing in 5G Heterogeneous Networks
Андраби У. М., Wadood E., Ojha S. K. и др., IEEE Access 2026 Vol. 14 P. 103358–103375
Добавлено: 23 сентября 2026 г.
LLM-assisted writing and citation advantage: evidence from scientific publications before and after ChatGPT release
Паклина С. Н., Паршаков П. А., Elena Rapoport, Scientometrics 2026 P. 1–26
Добавлено: 23 сентября 2026 г.
Label-Free Quantification in the Crux Toolkit
Кертес-Фаркаш А., Аквей Ф. Л., Journal of Proteome Research 2026 Vol. 25 P. 3764–3768
Добавлено: 23 сентября 2026 г.
Risk Assessment Models for Heated Tobacco Products
Maddalena L., Yildiz B., Del Vecchio Blanco F. и др., Risk Analysis 2026 Vol. 46 No. 4 P. 1–26
Добавлено: 22 сентября 2026 г.
On efficient algorithms for bottleneck path problems with many sources
Kirill V. Kaymakov, Dmitry S. Malyshev, Optimization Letters 2024 Vol. 18 P. 1273–1283
Добавлено: 18 апреля 2024 г.
A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
Малышев Д. С., Duginov O. I., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 4 P. 791–801
Добавлено: 16 февраля 2024 г.
Comparative Analysis of Logic Reasoning and Graph Neural Networks for Ontology-Mediated Query Answering with a Covering Axiom
Герасимова О. А., Макаров И. А., Severin N., IEEE Access 2023 Vol. 11 P. 88074–88086
The problem of query answering over incomplete attributed graph data is a challenging field of database management systems and artificial intelligence. When there are rules on data structure expressed in the form of the ontology, the theoretical complexity of finding exact solution satisfying ontology constraints increases. Logic-based methods use theoretical constructions to obtain efficient rewritings ...
Добавлено: 5 января 2024 г.
The discrete Fourier transform over the binary finite field
Sergei Valentinovich Fedorenko, IEEE Access 2023 Vol. 11 P. 62771–62779
Добавлено: 19 июля 2023 г.
Complexity function and complexity of validity of modal and superintuitionistic propositional logics
Рыбаков М. Н., Shkatov D., Journal of Logic and Computation 2023 Vol. 33 No. 7 P. 1566–1595
Добавлено: 6 января 2023 г.
Some cases of polynomial solvability of the edge coloring problem that are generated by forbidden 8-edge subcubic forests
Малышев Д. С., Duginov O. I., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2022 Vol. 16 P. 276–291
Добавлено: 31 декабря 2022 г.
  • О ВЫШКЕ
  • Цифры и факты
  • Руководство и структура
  • Устойчивое развитие в НИУ ВШЭ
  • Преподаватели и сотрудники
  • Корпуса и общежития
  • Закупки
  • Обращения граждан в НИУ ВШЭ
  • Фонд целевого капитала
  • Противодействие коррупции
  • Сведения о доходах, расходах, об имуществе и обязательствах имущественного характера
  • Сведения об образовательной организации
  • Людям с ограниченными возможностями здоровья
  • Единая платежная страница
  • Работа в Вышке
  • ОБРАЗОВАНИЕ
  • Лицей
  • Довузовская подготовка
  • Олимпиады
  • Прием в бакалавриат
  • Вышка+
  • Прием в магистратуру
  • Аспирантура
  • Дополнительное образование
  • Центр развития карьеры
  • Бизнес-инкубатор ВШЭ
  • Образовательные партнерства
  • Обратная связь и взаимодействие с получателями услуг
  • НАУКА
  • Научные подразделения
  • Исследовательские проекты
  • Мониторинги
  • Диссертационные советы
  • Защиты диссертаций
  • Академическое развитие
  • Конкурсы и гранты
  • Внешние научно-информационные ресурсы
  • РЕСУРСЫ
  • Библиотека
  • Издательский дом ВШЭ
  • Книжный магазин «БукВышка»
  • Типография
  • Медиацентр
  • Журналы ВШЭ
  • Публикации
  • http://www.minobrnauki.gov.ru/
    Министерство науки и высшего образования РФ
  • https://edu.gov.ru/
    Министерство просвещения РФ
  • https://elearning.hse.ru/mooc
    Массовые открытые онлайн-курсы
  • НИУ ВШЭ1993–2026
  • Адреса и контакты
  • Условия использования материалов
  • Политика обработки персональных данных
  • Правила применения рекомендательных технологий в НИУ ВШЭ
  • Карта сайта
Редактору