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

Статья

О сложности задачи о доминирующем множестве в подклассах класса расщепляемых графов

Замараев В. А., Малышев Д. С., Мокеев Д. Б.

Известно, что задача о доминирующем множестве в классе расщепляемых графов NP-полна. Изучается влияние степеней некоторых вершин таких графов на вычислительную сложность этой задачи.