Combinatorics and algorithms for quasi-chain graphs

Alecu B.; Atminas A.; Loozin V. V.; D. Malyshev

doi:10.1007/978-3-030-79987-8_4

АБВ
АБВ
АБВ

Обычная версия сайта

Приоритетные направления

по году

Тематика

Новости

19 мая 2026 г.

Физики НИУ ВШЭ выяснили, что происходит внутри устойчивого вихря

В атмосфере и в океане часто наблюдаются крупные вихри с характерными спиральными рукавами. Физики из НИУ ВШЭ объяснили, как они формируются и почему сохраняют свою структуру. Оказалось, что скорости в точках, расположенных вдоль одной дуги вихря, остаются связанными даже на больших расстояниях. При этом в направлении от центра вихря эта связь быстро ослабевает. Такие различия помогают объяснить образование рукавов и могут улучшить модели атмосферных и океанических течений. Результаты опубликованы в Physical Review Fluids.

18 мая 2026 г.

В Вышке прошла XXX юбилейная научно-техническая конференция имени Е.В. Арменского

Организатором научного события выступает Московский институт электроники и математики им. А.Н. Тихонова ВШЭ. В этом году главный инженерный студенческий форум проходил 30-й раз и собрал рекордное число участников. Студенты, аспиранты и молодые специалисты из 50 вузов и организаций России представили научно-исследовательские доклады в ИТ-области. Отдельная секция была посвящена научно-исследовательским работам школьников.

15 мая 2026 г.

В НИУ ВШЭ разрабатывают нейросеть для сферы науки и инноваций

Исследователи НИУ ВШЭ учат большие языковые модели понимать русскоязычную научную терминологию, увеличивая при этом их энергоэффективность. Адаптированная модель работает в 2,7 раза быстрее и требует на 73% меньше памяти, чем исходная открытая модель, что позволяет запускать ее на более доступном оборудовании. Программа прошла государственную регистрацию.

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

Публикации

?

Combinatorics and algorithms for quasi-chain graphs

P. 49–62.

Alecu B., Atminas A., Loozin V. V., Малышев Д. С.

Язык: английский

Полный текст

DOI

Текст на другом сайте

Ключевые слова: polynomial-time algorithm bipartite chain graphs implicit representation

В книге

International Workshop on Combinatorial Algorithms, 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5–7, 2021

Vol. 12757. , Springer, 2021.

Combinatorics and Algorithms for Quasi-Chain Graphs

Alecu B., Atminas A., Vadim Lozin и др., Algorithmica 2023 Vol. 85 No. 3 P. 642–664

Добавлено: 8 августа 2022 г.

Rescheduling Traffic on a Partially Blocked Segment of Railway with a Siding

Zinder Y., Лазарев А. А., Мусатова Е. Г., Automation and Remote Control 2020 Vol. 81 No. 6 P. 955–966

Добавлено: 1 сентября 2020 г.

The weighted coloring problem for two graph classes characterized by small forbidden induced structures

Малышев Д. С., Discrete Applied Mathematics 2018 Vol. 247 P. 423–432

Добавлено: 23 апреля 2018 г.

More results on weighted independent domination

Lozin V. V., Малышев Д. С., Mosca R. и др., Theoretical Computer Science 2017 Vol. 700 P. 63–74

Добавлено: 28 августа 2017 г.

The Complexity of the Vertex 3-Colorability Problem for Some Hereditary Classes Defined By 5-Vertex Forbidden Induced Subgraphs

Малышев Д. С., Graphs and Combinatorics 2017 Vol. 33 No. 4 P. 1009–1022

Добавлено: 26 мая 2017 г.

Two complexity results for the vertex coloring problem

Малышев Д. С., Развенская О. О., Discrete Applied Mathematics 2017 Vol. 219 P. 158–166

Добавлено: 21 ноября 2016 г.

Efficient algorithms for the recognition of topologically conjugate gradient-like diffeomorhisms

Гринес В. З., Малышев Д. С., Починка О. В. и др., Regular and Chaotic Dynamics 2016 Vol. 21 No. 2 P. 189–203

Добавлено: 5 апреля 2016 г.

Critical hereditary graph classes: a survey

Малышев Д. С., Пардалос П. О., Optimization Letters 2016 Vol. 10 No. 8 P. 1593–1612

Добавлено: 18 декабря 2015 г.

A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs

Малышев Д. С., Discrete Applied Mathematics 2016 Vol. 203 P. 117–126

Добавлено: 9 октября 2015 г.

A complexity dichotomy for the dominating set problem

Малышев Д. С., / Series "Working papers by Cornell University". 2015.

Добавлено: 2 июня 2015 г.

A complexity dichotomy and a new boundary class for the dominating set problem

Малышев Д. С., Journal of Combinatorial Optimization 2016 Vol. 32 No. 1 P. 226–243

Добавлено: 4 апреля 2015 г.

Vertex coloring of graphs with few obstructions

Лозин В. В., Малышев Д. С., Discrete Applied Mathematics 2017 Vol. 216 P. 273–280

We study the vertex coloring problem in classes of graphs defined by finitely many forbidden induced subgraphs. Of our special interest are the classes defined by forbidden induced subgraphs with at most 4 vertices. For all but three classes in this family we show either NP-completeness or polynomial-time solvability of the problem. For the remaining ...

Добавлено: 3 марта 2015 г.

Two cases of polynomial-time solvability for the coloring problem

Малышев Д. С., Journal of Combinatorial Optimization 2016 Vol. 31 No. 2 P. 833–845

Добавлено: 18 сентября 2014 г.

The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs

Малышев Д. С., Discrete Mathematics 2015 Vol. 338 No. 11 P. 1860–1865

We completely determine the complexity status of the 3-colorability problem for hereditary graph classes defined by two forbidden induced subgraphs with at most five vertices. © 2015 Elsevier B.V. All rights reserved. ...

Добавлено: 7 апреля 2014 г.

The coloring problem for classes with two small obstructions

Малышев Д. С., Optimization Letters 2014 Vol. 8 No. 8 P. 2261–2270

The coloring problem is studied in the paper for graph classes defined by two small forbidden induced subgraphs. We prove some sufficient conditions for effective solvability of the problem in such classes. As their corollary we determine the computational complexity for all sets of two connected forbidden induced subgraphs with at most five vertices except ...

Добавлено: 6 марта 2014 г.

The coloring problem for classes with two small obstructions

Малышев Д. С., / Series math "arxiv.org". 2013. No. 1307.0278v1.

Добавлено: 3 октября 2013 г.