Аннотация:
Понятия граничного и минимального сложного классов графов, объединённые общим термином «критический класс», являются полезными инструментами для анализа вычислительной сложности задач на графах в семействе наследственных классов графов. В данном семействе для нескольких задач на графах известны граничные классы. В этой работе критические классы графов рассматриваются применительно к семействам сильно наследственных и минорно замкнутых классов. До результатов настоящей работы имелся пример только одной задачи на графах, для которой в семействе сильно наследственных классов выявлены граничные классы. Более того, в семействе минорно замкнутых классов ни для одной задачи на графах не было известно ни одного граничного класса. В настоящей работе для обоих рассматриваемых семейств и нескольких классических задач на графах приводятся полные описания граничных классов. Для задачи 2-аддитивной аппроксимации ленточной ширины графа в семействе минорно замкнутых классов найден граничный класс, причём для двух других семейств критические классы для этой задачи не известны. Библиогр. 21.
Исследование выполнено при финансовой поддержке Российского фонда фундаментальных исследований (проекты 16–31–60008-мол а дк, 16–01–00599-а, 16–31–00109-мол а), гранта Президента РФ MK–4819.2016.1,
а также лаборатории алгоритмов и технологий анализа сетевых структур НИУ ВШЭ.
Статья поступила: 11.01.2016 Переработанный вариант: 29.04.2016
Образец цитирования:
Д. С. Малышев, “Критические элементы в комбинаторно замкнутых семействах классов графов”, Дискретн. анализ и исслед. опер., 24:1 (2017), 81–96; J. Appl. Industr. Math., 11:1 (2017), 99–106
\RBibitem{Mal17}
\by Д.~С.~Малышев
\paper Критические элементы в комбинаторно замкнутых семействах классов графов
\jour Дискретн. анализ и исслед. опер.
\yr 2017
\vol 24
\issue 1
\pages 81--96
\mathnet{http://mi.mathnet.ru/da864}
\crossref{https://doi.org/10.17377/daio.2017.24.523}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3622066}
\elib{https://elibrary.ru/item.asp?id=28905206}
\transl
\jour J. Appl. Industr. Math.
\yr 2017
\vol 11
\issue 1
\pages 99--106
\crossref{https://doi.org/10.1134/S1990478917010112}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85013983205}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da864
https://www.mathnet.ru/rus/da/v24/i1/p81
Эта публикация цитируется в следующих 3 статьяx:
Dmitry Gribanov, Ivan Shumilov, Dmitry Malyshev, Panos Pardalos, “On Δ-modular integer linear problems in the canonical form and equivalent problems”, J Glob Optim, 88:3 (2024), 591
Gribanov V D. Zolotykh N.Yu., “On Lattice Point Counting in Delta-Modular Polyhedra”, Optim. Lett., 16:7 (2022), 1991–2018
D. V. Gribanov, Springer Proceedings in Mathematics & Statistics, 247, Computational Aspects and Applications in Large-Scale Networks, 2018, 19
Цитирование в формате AMSBIB
Обратная связь: