RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2012, том 24, выпуск 4, страницы 91–103 (Mi dm1213)

Экстремальные множества графов при решении задачи демаркации в семействе наследственно замкнутых классов графов

Д. С. Малышев


Аннотация: В данной работе рассматриваются понятия минимального сложного и граничного классов. Данные классы играют особую роль при определении границы между полиномиальной разрешимостью и $NP$-полнотой задач на графах в семействе наследственных классов. Ранее в одной из работ автора было установлено, что для некоторого типа задач на графах минимальных сложных классов нет. В данной работе, наоборот, доказывается достаточное условие существования таких классов. Его действенность подтверждается новыми примерами минимальных сложных классов и граничных классов для некоторых задач на графах. Для выявленных задач удается полностью описать множества минимальных сложных и граничных классов. Ранее ни для одной задачи на графах таких описаний получить не удавалось.
Работа выполнена при поддержке РФФИ, проекты 10–01–00357-a и 11–01–00107-a, и ФЦП “Научные и научно-педагогические кадры инновационной России на 2009–2012 гг.”, ГК 16.740.11.0310.

УДК: 519.17

Статья поступила: 07.07.2011

DOI: 10.4213/dm1213


 Англоязычная версия: Discrete Mathematics and Applications, 2012, 22:5-6, 595–608

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


© МИАН, 2024