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

В ситуации, описываемой леммой, можно сказать, что мы можем кернелизовать исходные экземпляры до экземпляров размером не более g(k). Два этих класса задач тесно связаны, однако результаты их выполнения различаются. Наилучший известный FPT-алгоритм задачи построения максимального листового остовного дерева с временем выполнения O*(8.12) предложил Бонсма [ ] на основе подхода на базе экстремальных структур, который разработали Эстивилл-Кастро, Феллоуз, Лэнгстон и Розамонд [8]. Этот алгоритм определяет, имеет ли граф G с n вершинами остовное дерево не менее чем с k листьями. В то же время авторы работы [8] представили FPT-алгоритм с наименьшим размером ядра.