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

Статья

Analysis of the Impact of the Number of Edges in Connected Graphs on the Time Complexity of an Independent Set Problem

Journal of Applied and Industrial Mathematics. 2011. Vol. 18. No. 3. P. 1-4.

Изучается сложностной статус задачи о независимом множестве в классах связных графов, определяемых функциональными ограничениями числа ребер от числа вершин. Показано, что для любого натурального C в классе графов  ∞Sn=1{G | |V (G)| = n,|E(G)| 6 n + C[log2(n)]} эта задача полиномиально разрешима. С другой стороны, доказано, что она не является полиномиально разрешимой в классе графов  ∞Sn=1{G | |V (G)| = n,|E(G)| 6 n + C[log2(n)]}  для любой неограниченной неубывающей функции f(n) : N → N, экспонента от которой растет быстрее, чем полином от n. Последний результат справедлив, если для задачи о независимом множестве нет субэкспоненциальных алгоритмов.