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

Статья

Влияние роста упаковочного числа графов на сложность задачи о независимом множестве

Дискретная математика. 2013. Т. 25. № 2. С. 63-67.

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