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

Статья

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

Задача о независимом множестве для заданного обыкновенного графа состоит в вычислении размера наибольшего множества его попарно несмежных вершин. В данной работе доказываем полиномиальную разрешимость этой задачи для субкубических планарных графов, не содержащих порождённого дерева, получаемого отождествлением концов трёх путей длины 3, 3 и 2 соответственно.