RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискретн. анализ и исслед. опер.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Дискретн. анализ и исслед. опер., 2017, том 24, номер 1, страницы 81–96 (Mi da864)  

Критические элементы в комбинаторно замкнутых семействах классов графов

Д. С. Малышевab

a Нижегородский гос. университет им. Н. И. Лобачевского, пр. Гагарина, 23, 603950 Нижний Новгород, Россия
b Национальный исследовательский университет «Высшая школа экономики», ул. Большая Печёрская, 25/12, 603155 Нижний Новгород, Россия

Аннотация: Понятия граничного и минимального сложного классов графов, объединённые общим термином «критический класс», являются полезными инструментами для анализа вычислительной сложности задач на графах в семействе наследственных классов графов. В данном семействе для нескольких задач на графах известны граничные классы. В этой работе критические классы графов рассматриваются применительно к семействам сильно наследственных и минорно замкнутых классов. До результатов настоящей работы имелся пример только одной задачи на графах, для которой в семействе сильно наследственных классов выявлены граничные классы. Более того, в семействе минорно замкнутых классов ни для одной задачи на графах не было известно ни одного граничного класса. В настоящей работе для обоих рассматриваемых семейств и нескольких классических задач на графах приводятся полные описания граничных классов. Для задачи $2$-аддитивной аппроксимации ленточной ширины графа в семействе минорно замкнутых классов найден граничный класс, причём для двух других семейств критические классы для этой задачи не известны. Библиогр. 21.

Ключевые слова: вычислительная сложность, наследственный класс, критический класс, эффективный алгоритм.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 16-31-60008_мол_а_ дк
16-01-00599_а
16-31-00109_мол_а
Министерство образования и науки Российской Федерации MK-4819.2016.1
Исследование выполнено при финансовой поддержке Российского фонда фундаментальных исследований (проекты 16–31–60008-мол а дк, 16–01–00599-а, 16–31–00109-мол а), гранта Президента РФ MK–4819.2016.1, а также лаборатории алгоритмов и технологий анализа сетевых структур НИУ ВШЭ.


DOI: https://doi.org/10.17377/daio.2017.24.523

Полный текст: PDF файл (344 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2017, 11:1, 99–106

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.17
Статья поступила: 11.01.2016
Переработанный вариант: 29.04.2016

Образец цитирования: Д. С. Малышев, “Критические элементы в комбинаторно замкнутых семействах классов графов”, Дискретн. анализ и исслед. опер., 24:1 (2017), 81–96; J. Appl. Industr. Math., 11:1 (2017), 99–106

Цитирование в формате AMSBIB
\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://www.ams.org/mathscinet-getitem?mr=3622066}
\elib{http://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{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85013983205}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da864
  • http://mi.mathnet.ru/rus/da/v24/i1/p81

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:2611
    Полный текст:10
    Литература:20
    Первая стр.:11
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020