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

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

doi:10.4213/dm1440

Публикации

?

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

Дискретная математика. 2017. Т. 29. № 3. С. 114–125.

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

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

Научное направление: Компьютерные науки Математика

Приоритетные направления: компьютерно-математическое математика

Язык: русский

Полный текст

DOI

Ключевые слова: вычислительная сложность независимое множество планарный граф плоская триангуляция

Aerokinesis: An IoT-Based Vision-Driven Gesture Control System for Quadcopter Navigation Using Deep Learning and ROS2

Pikalov V., Meshcheryakov V., Kondratev S. и др., Technologies 2026 Vol. 14 No. 1 P. 1–27

This paper presents Aerokinesis, an IoT-based software–hardware system for intuitive gesture-driven control of quadcopter unmanned aerial vehicles (UAVs), developed within the Robot Operating System 2 (ROS2) framework. The proposed system addresses the challenge of providing an accessible human–drone interaction interface for operators in scenarios where traditional remote controllers are impractical or unavailable. The architecture comprises ...

Добавлено: 19 мая 2026 г.

Aerokinesis: An IoT-Based Vision-Driven Gesture Control System for Quadcopter Navigation Using Deep Learning and ROS2

Кондратьев С., Никитин Г. Э., Дырченкова Ю. А. и др., Technologies 2026 Vol. 14 No. 1 P. 1–27

Добавлено: 19 мая 2026 г.

On smooth Fano threefolds with coregularity zero

Жакупов О. Б., European Journal of Mathematics 2025 Vol. 11 Article 84

Добавлено: 18 мая 2026 г.

Parallel Computational Technologies. PCT 2025

Springer, 2025.

Добавлено: 18 мая 2026 г.

KMHCR: A Key-Controlled Signal-Domain Transformation for 5G IoT Security

Ronglin Z., Wei L., Jiahong C. и др., Journal of Signal Processing Systems 2026 Vol. 98 P. 1–15

Добавлено: 16 мая 2026 г.

DPN Verifier: A Toolkit for Faster Soundness Verification and Repair of Process Models with Data

Суворов Н. М., Proceedings of the Institute for System Programming of the RAS 2026 Vol. 38 No. 3(2) P. 49–66

Сети Петри с данными (DPN) являются расширением классических сетей Петри, позволяющим моделировать процессы, где данные влияют на поток управления, обеспечивая комплексное представление о поведении системы и возможность обнаружения точек отказа, которые в противном случае были бы скрыты. Одним из критериев корректности для моделей процессов является бездефектность. Модель процесса называется бездефектной, если она всегда корректно завершается ...

Добавлено: 16 мая 2026 г.

2-Elliptic Periodic Orbits near a Nonsimple Homoclinic Tangency in Four-Dimensional Symplectic Maps

Lerman L. M., Turaev D. V., Regular and Chaotic Dynamics 2026 Vol. 31 No. 3 P. 349–369

Добавлено: 15 мая 2026 г.

Bibliometric Analysis by Network Models

Алескеров Ф. Т., Якуба В. И., Khutorskaya O. и др., Springer, 2026.

Добавлено: 15 мая 2026 г.

Neural-network maps for two-parameter modeling of bistability and codimension-two bifurcations in two-dimensional flow dynamical systems

Купцов П. В., Панюшев А. А., Станкевич Н. В., Chaos 2026 Vol. 36 No. 5 Article 053138

Добавлено: 15 мая 2026 г.

Bifurcations and Structural Stability of Generic PC-HC Families

Доровский А. А., / Series arXiv "math". 2026.

Добавлено: 14 мая 2026 г.

The Sobolev space W_2^{1/2}: Simultaneous improvement of functions by a homeomorphism of the circle

Лебедев В. В., Journal of Mathematical Analysis and Applications 2026 Vol. 563 No. 2 Article 130787

Добавлено: 14 мая 2026 г.

QGKM: A Quantum Fidelity-Based Graph Clustering Framework for Robust Data Pattern Recognition in Education Social Networks QGKM: A Quantum Fidelity-Based Graph Clustering Framework for Robust Data Pattern Recognition in Education Social Networks

Neal N. X., Weiqing L., Dacheng H. и др., Algorithms 2026 Vol. 19 No. 5 P. 1–22

Добавлено: 13 мая 2026 г.

Symmetric Cubic Polynomials

Blokh A., Oversteegen L., Selinger N. и др., Arnold Mathematical Journal 2025 Vol. 12 No. 1 P. 1–40

Добавлено: 13 мая 2026 г.

Proceedings of the 9th Student Research Workshop associated with the International Conference Recent Advances in Natural Language Processing

Velichkov B., Nikolova-Koleva I., Slavcheva M., Shumen: INCOMA Ltd, 2025.

Добавлено: 12 мая 2026 г.

Игры на сетях с линейным наилучшим ответом: модели и методы управления

Петров И. В., Автоматика и телемеханика 2026 № 6 С. 82–118

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

Добавлено: 12 мая 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 г.

Natural hazard database from Internet publications: text mining with a large language model

Деркачева А. А., Сакиркина М. А., Краев Г. Н. и др., /. 2026.

Добавлено: 28 апреля 2026 г.

Ising models on the hydrogen peroxide and other lattices

Qin X., Deng Y., Щур Л. Н. и др., / Series arXiv "math". 2026. No. 2603.02962.

Добавлено: 20 апреля 2026 г.

Algorithmic overlaps as thermodynamic variables: from local to cluster Monte Carlo dynamics in critical phenomena

Пиле Я. Э., Deng Y., Щур Л. Н., / Series arXiv "math". 2026. No. 2604.10254.

Добавлено: 20 апреля 2026 г.

On weak solutions to the 1d compressible Navier-Stokes equations: a Lipschitz continuous dependence on data in weaker norms and an error of their homogenization

Zlotnik Alexander, / Series arXiv "math". 2026. No. 2602.03481v1.

Добавлено: 18 апреля 2026 г.

On the dimension of the space of static potentials on three-manifolds

Медведев В. О., / Series arXiv "math". 2026.

We investigate the interplay between the dimension of the space of static potentials and the geometric and topological structure of the underlying static three-manifold. A partial classification of boundaryless static manifolds is obtained in terms of this dimension. We also treat the case of static manifolds with boundary. In particular, we prove that if a ...

Добавлено: 3 апреля 2026 г.

Using predefined vector systems to speed up neural network multimillion class classification

Gabdullin N., Андросов И. А., / Series Computer Science "arxiv.org". 2026.

Добавлено: 2 апреля 2026 г.

О СЛОЖНОСТИ ПРОБЛЕМЫ ТОТАЛЬНОЙ ВЫВОДИМОСТИ В НЕУКОРАЧИВАЮЩИХ И КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИКАХ

Дудаков С. М., Карлов Б. Н., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 Т. 524 № 1 С. 11–18

В работе изучается проблема тотальной выводимости в контекстно-свободных, неукорачивающих и контекстно-зависимых грамматиках. Для фиксированного терминального слова проблема состоит в том, чтобы по грамматике определить, существует ли вывод этого слова, в котором каждое правило используется не менее некоторого заданного числа раз. Доказывается, что проблема тотальной выводимости пустого слова в контекстно-свободной грамматике является NP-полной. Для неукорачивающих и ...

Добавлено: 18 марта 2026 г.