• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

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

Дискретная математика. 2012. Т. 24. № 4. С. 91-103.

В данной работе рассматриваются понятия минимального сложного и граничного классов. Данные классы играют особую роль при определении границы между полиномиальной разрешимостью и NP-полнотой задач на графах в семействе наследственных классов. Ранее в одной из работ автора было установлено, что для некоторого типа задач на графах минимальных сложных классов нет. В данной работе, наоборот,

доказывается достаточное условие существования таких классов. Его действенность подтверждается новыми примерами минимальных сложных классов и граничных классов для некоторых задач на графах. Для выявленных задач удается полностью описать множества минимальных сложных и граничных классов. Ранее ни для одной задачи на графах таких описаний получить не удавалось.