Остовное дерево с максимальным количеством листьев: различия между версиями

Можно выделить пять независимых объектов, связанных с теорией экстремальных структур и иллюстрирующих все цели алгоритма построения максимального листового остовного дерева. Перечислим эти пять целей:

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

(б) Правила мощной предварительной обработки (редукции данных / кернелизации) и комбинации правил, которые могут использоваться независимо от того, насколько мал параметр, и могут комбинироваться с другими подходами – например, аппроксимацией и эвристиками. Обычно они несложны для программирования.

(в) Градиенты и правила преобразования для эвристик локального поиска.

(г) Алгоритмы аппроксимации с полиномиальным временем исполнения и границы эффективности, доказанные систематическим образом.

(д) Структура, используемая для решения других задач.