Сложность некоторых задач на графах с ограниченными минорами их матриц ограничений

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

?

Сложность некоторых задач на графах с ограниченными минорами их матриц ограничений

Журнал Средневолжского математического общества. 2016. Т. 18. № 3. С. 19–31.

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

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

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

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

Полный текст

Ключевые слова: комбинаторная оптимизация independent set problem задача о независимом множестве вычислительная сложность эффективный алгоритм задача о доминирующем множестве combinatorial optimization дискретная оптимизация integer linear programming целочисленное линейное программирование discrete optimization Integer programming efficient algorithm целочисленное программирование алгоритмическая сложность dominating set problem Computational Complexity Matrix minors миноры матриц

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 г.

Интегрированная среда моделирования для верификации и валидации программ управления подключенными и высокоавтоматизированными транспортными средствами

Степанянц В. Г., Долгов И. М., Хорошилов Г. С. и др., Труды Института системного программирования РАН 2026 Т. 38 № 3 С. 95–110

На рынок постепенно выходят высокоавтоматизированные и подключенные транспортные средства (ТС). В настоящее время предлагаются решения, позволяющие использовать эти технологии для совместного управления дорожным движением, что может значительно повысить его безопасность. В статье анализируются требования к интегрированной среде моделирования подключенных и высокоавтоматизированных ТС и совместной автоматизации управления дорожным движением с высокодетализированным учетом влияния окружающих объектов. Проанализированы ...

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

Connected and Automated Vehicle Scenario Manager Graphical User Interface

Тихонов Р. А., Efendiev M. T., Fedotenkov A. A., 2026 International Russian Smart Industry Conference (SmartIndustryCon) 2026 P. 542–547

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

Архимед: научно-методический сборник

М.: ООО «Макс Пресс», 2026.

В настоящем сборнике представлены тезисы докладов участников семинара "Интеграция основного и дополнительного физико-математического образования", проходившего 11 февраля 2026 года в ГБОУ Школа №2007 ФМШ г. москвы, а также другие публикации, посвящённые вопросам дополнительного физико-математического образования. ...

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

A two-point phase recovering from holographic data on a single plane

Novikov R., Сивкин В. Н., Inverse Problems 2026 Vol. 42 No. 4 Article 045009

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

Multivariate Newton interpolation in downward closed spaces reaches the optimal Bernstein–Walsh approximation rate

Hecht M., Hofmann P., Wicaksono D. и др., IMA Journal of Numerical Analysis 2026 Vol. 00 P. 1–30

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

Proceedings 2026 IEEE 11th International Conference on Smart Cloud SmartCloud 2026 8-10 May 2026

Los Alamitos: IEEE Computer Society, 2026.

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

От неизвестности к прозрачности: обзор технологий объяснимого ИИ (XAI)

Авдошин С. М., Песоцкая Е. Ю., Информационные технологии 2026 Т. 32 № 4 С. 185–194

С развитием ИИ, и в особенности глубокого обучения, появились модели, способные давать крайне точные прогнозы. Однако их внутренняя логика остается трудной для понимания — и это серьезная проблема, особенно в сферах, где от корректности алгоритма зависят критиче ски важные решения. Одним из перспективных путей ее решения считается направление Explainable Artificial Intelligence (XAI) — разработка подходов, позволяющих прояснять ...

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

Explainable AI for Industry 5.0: Shedding light on the black box

Авдошин С. М., Песоцкая Е. Ю., Business Informatics 2026 Vol. 20 No. 1 P. 7–28

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

Comparative Analysis of Students’ Perceptions of Programming Puzzles: Parson’s and Wordle-Like

Варнавский А. Н., IEEE Access 2026 Vol. 14 P. 37487–37508

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

Towards performance analysis of GPU-aware MPI over Angara interconnect

Ismagilov T., Mukosey A., Смирнов Ф. А. и др., International Journal of High Performance Computing Applications 2026 Vol. 40 No. 2 P. 240–253

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

Weighted Chernoff Information and Optimal Loss Exponent in Context-Sensitive Hypothesis Testing

Кельберт М. Я., Kalimulina E. Y., Entropy 2026 Vol. 28 Article 536

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

Calogero–Sutherland hyperbolic system and Heckman–Opdam $$\mathfrak {gl}_n$$ gl n hypergeometric function

Белоусов Н. М., Черепанов Л. К., Деркачов С. Э. и др., Selecta Mathematica, New Series 2026 Vol. 32 Article 44

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

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 г.

Homogeneous maximizers of the Blaschke-Santalo-type functionals

Колесников А. В., / Series arXiv "math". 2025.

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