Критические классы графов для задачи о реберном списковом ранжировании

Д. С. Малышев

?

Критические классы графов для задачи о реберном списковом ранжировании

Дискретный анализ и исследование операций. 2013. Т. 20. № 6. С. 59–76.

Задача о реберном списковом ранжировании является обобщением классической задачи о раскраске ребер графа и математической моделью протекания ряда параллельных процессов. В настоящей работе исследуется вычислительная сложность данной задачи для замкнутых относительно изоморфизма и удаления вершин множеств графов (наследственных классов). Описываются все конечно определенные и минорно замкнутые случаи, для которых эта задача полиномиально разрешима. Выявляется вся совокупность "критических" классов графов, включение которых в конечно определенный класс эквивалентно "труднорешаемости" задачи о реберном списковом ранжировании в этом классе. По-видимому, это вообще первый результат о полном таком описании для неискусственных NP-полных задач на графах. Конструктивно доказывается, что для этой задачи среди минимальных по включению наследственных случаев "труднорешаемости" имеется всего 5 конечно определенных классов и 1 минорно замкнутый класс

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

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

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

Полный текст

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

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:

Исследование "критических" наследственных классов графов (2013)

Amplifying Latent Safety in Large Language Models via Gated Activation Steering

Roman Prosvirnin, Suslov A., Aleksei Soldatov и др., Computation 2026 Vol. 14 No. 10 Article 261

Добавлено: 27 октября 2026 г.

PACTraD: Multi-Task Benchmark and Domain-Specific Attention Mechanism for Wildlife Classification, Detection, and Segmentation in Protected Area Camera Trap Data

Aleksei Samarin, Назаренко А. А., Nazarenko D. и др., Big Data and Cognitive Computing 2026 Vol. 10 No. 11 P. 1–52

Добавлено: 27 октября 2026 г.

2026 10th Scientific School Dynamics of Complex Networks and their Applications

IEEE, 2026.

Добавлено: 26 октября 2026 г.

A Curated Dataset for Chemical Characterization of Heated Tobacco Product Aerosol

Maddalena L., Yildiz B., Del Vecchio Blanco F. и др., Scientific data 2026 P. 1–20

Добавлено: 26 октября 2026 г.

Weakly non-integrable solitary wave collisions in the modified Benjamin–Bona–Mahony equation

Flamarion M. V., Пелиновский Е. Н., Wave Motion 2027 Vol. 148 Article 103867

Добавлено: 23 октября 2026 г.

A Multi-Feature Fusion Deep Neural Network with Attention for Multi-Task Crop Monitoring

Obsie E. Y., Zhan Y., Liu Y., Engineering Research Express 2026 Article 7

Добавлено: 22 октября 2026 г.

A Neural Network Approach for Generating Libration Point Orbits

Lev Pyatko, Sergey Aksenov, Regular and Chaotic Dynamics 2026 Vol. 31 No. 5 P. 794–813

In the circular restricted three-body problem, families of periodic and quasi-periodic orbits exist in the vicinity of the libration points and are of significant interest for practical applications. This work presents a neural network-based algorithm for orbit construction and station-keeping, applicable to both periodic and quasi-periodic orbits near collinear libration points. The method employs a ...

Добавлено: 19 октября 2026 г.

Основы теории информации

Воронцова Т. Д., М.: Академия, 2025.

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

Добавлено: 19 октября 2026 г.

Моментные оценки для стохастической аппроксимации

Наумов А. А., Рубцов А. С., Самсонов С. В. и др., Успехи математических наук 2026 Т. 81 № 4 (490) С. 161–162

Краткое сообщение рассматривает Моментные оценки для стохастической аппроксимации ...

Добавлено: 17 октября 2026 г.

An infinite series of Gorenstein local algebras failing the affine homogeneity property

Roman Avdeev, Yulia Zaitseva, Mediterranean Journal of Mathematics 2026 Vol. 23 No. 7 Article 224

Добавлено: 17 октября 2026 г.

Turbulent Exchange Tensor in the Atmospheric Boundary Layer: An Inverse-Problem Approach Using Radiosonde Wind Observations with High Vertical Resolution

Гордин В. А., Ефременко Д. С., Boundary-Layer Meteorology 2026 Vol. 192 No. 51

An inverse problem of reconstructing the turbulent exchange tensor from large archives of observed wind profiles within the Åkerblom–Ekman (A-E) model framework is investigated using high-vertical-resolution radiosonde observations. The reconstructed tensor provides improved agreement between modeled and observed wind profiles compared to classical formulations based on real turbulent exchange coefficient. Instead of the classical A-E ...

Добавлено: 16 октября 2026 г.

Diversity of chaos with additional zero Lyapunov exponents in heterogeneous ensemble of quasi-periodic and chaotic systems

Kuznetsov A. P., Sedova Y. V., Станкевич Н. В., Chaos, Solitons and Fractals 2026 Vol. 213 No. 12 Article 119309

Добавлено: 16 октября 2026 г.

A Reproducible Microscopy Acquisition Pipeline and Microscopy-Aware Attention for Classification, Detection, and Segmentation of Microorganisms

Aleksei Samarin, Назаренко А. А., Nazarenko D. и др., Machine Learning and Knowledge Extraction 2026 Vol. 8 No. 10 Article 330

Добавлено: 14 октября 2026 г.

A Three-Party W-State Quantum Secret Sharing Protocol with X-Gate Encoding and Forbidden-Outcome Detection

Timur Teregulov, Elena R. Loubenets, / Series Quantum Physics "arXiv". 2026. No. 2609.31472.

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

Pairings on the algebra of Laurent series over a ring

Левашев В. А., / Series arXiv "math". 2026. No. 2609.06010.

Добавлено: 24 сентября 2026 г.

Iterative construction of the R-matrices in arbitrary dimensions

Пятов П. Н., Пивоваров П. А., / Series math "arxiv.org". 2026. No. 2609.06274.

Добавлено: 24 сентября 2026 г.

On static manifolds with boundary admitting a nowhere-vanishing static potential

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

We study complete static manifolds with boundary admitting a nowhere-vanishing static potential. Our main result shows that, under a natural lower bound relating the scalar curvature and the boundary mean curvature, a simple static manifold with boundary must in fact have positive scalar curvature, negative boundary mean curvature, and be compact; we also obtain explicit ...

Добавлено: 19 сентября 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 г.