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

Статья

Расширяющие операторы для задачи о независимом множестве

Введено понятие расширяющего оператора для задачи о независимом множестве, являющееся полезным инструментом конструктивного формирования новых случаев эффективной разрешимости этой задачи в семействе наследственных классов графов. Данное понятие применяется к наследственным частям множества Free({P5,C5}). Доказано, что если для связного графа G задача полиномиально разрешима в классе Free({P5,C5,G}), то для любого p она остается таковой в классе Free({P5,C5,GK2,GK1,p}). Также найдены два новых наслед-

ственных подмножества Free({P5,C5}) с полиномиально разрешимой задачей о независимом множестве, не являющиеся следствием применения указанного оператора.