|
Дискретный анализ и исследование операций, 2009, том 16, выпуск 6, страницы 43–51
(Mi da593)
|
|
|
|
Эта публикация цитируется в 11 научных статьях (всего в 11 статьях)
О минимальных сложных классах графов
Д. С. Малышев Нижегородский государственный университет, г. Н. Новгород, Россия
Аннотация:
Рассматриваются понятия минимального сложного и граничного классов графов. Доказывается, что для задачи распознавания принадлежности наследственному классу графов не существует минимальных сложных классов. Указываются граничные и минимальные сложные классы графов для задач о списковом ранжировании. Эти классы графов являются первыми примерами минимальных сложных классов, а также первыми примерами сложных граничных классов. Библиогр. 9.
Ключевые слова:
вычислительная сложность, минимальный сложный класс, граничный класс, распознавание наследственного свойства, задачи о списковом ранжировании.
Статья поступила: 10.04.2009 Переработанный вариант: 20.07.2009
Образец цитирования:
Д. С. Малышев, “О минимальных сложных классах графов”, Дискретн. анализ и исслед. опер., 16:6 (2009), 43–51
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da593 https://www.mathnet.ru/rus/da/v16/i6/p43
|
Статистика просмотров: |
Страница аннотации: | 494 | PDF полного текста: | 97 | Список литературы: | 43 | Первая страница: | 7 |
|