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

Статья

Граничные классы для задач о списковом ранжировании относительно лесов

Малышев Д. С., Алексеев В. Е.

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