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

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

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


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




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

Дискретный анализ и исследование операций, 2017, том 24, выпуск 1, страницы 81–96
DOI: https://doi.org/10.17377/daio.2017.24.523 (Mi da864) 		 
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)

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

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

a Нижегородский гос. университет им. Н. И. Лобачевского, пр. Гагарина, 23, 603950 Нижний Новгород, Россия
b Национальный исследовательский университет «Высшая школа экономики», ул. Большая Печёрская, 25/12, 603155 Нижний Новгород, Россия
PDF полного текста (344 kB) Список цитирования (3)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.17377/daio.2017.24.523
Аннотация: Понятия граничного и минимального сложного классов графов, объединённые общим термином «критический класс», являются полезными инструментами для анализа вычислительной сложности задач на графах в семействе наследственных классов графов. В данном семействе для нескольких задач на графах известны граничные классы. В этой работе критические классы графов рассматриваются применительно к семействам сильно наследственных и минорно замкнутых классов. До результатов настоящей работы имелся пример только одной задачи на графах, для которой в семействе сильно наследственных классов выявлены граничные классы. Более того, в семействе минорно замкнутых классов ни для одной задачи на графах не было известно ни одного граничного класса. В настоящей работе для обоих рассматриваемых семейств и нескольких классических задач на графах приводятся полные описания граничных классов. Для задачи $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, а также лаборатории алгоритмов и технологий анализа сетевых структур НИУ ВШЭ.
Статья поступила: 11.01.2016
Переработанный вариант: 29.04.2016
Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2017, Volume 11, Issue 1, Pages 99–106
DOI: https://doi.org/10.1134/S1990478917010112
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.17
Образец цитирования: Д. С. Малышев, “Критические элементы в комбинаторно замкнутых семействах классов графов”, Дискретн. анализ и исслед. опер., 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://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:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Дискретный анализ и исследование операций
    Статистика просмотров:
    Страница аннотации:2745
    PDF полного текста:49
    Список литературы:47
    Первая страница:11
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024