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

Перейти к навигации Перейти к поиску
мНет описания правки
Строка 11: Строка 11:
Параметр: целое число k.
Параметр: целое число k.


Вопрос: имеет ли граф G с не менее чем k листьями?
Вопрос: имеет ли граф G остовное дерево с не менее чем k листьями?




Параметризованная сложность недетерминированного полного алгоритма ОДМЛ с полиномиальным временем выполнения широко изучалась [2, 3, 9, 11] с использованием кернелизации, ветвления и других техник с фиксированными параметрами (fixed-parameter tractable, FPT). Авторы работы [8] первыми предложили метод на базе экстремальной структуры для решения сложных вычислительных задач. Этот метод, напоминающий подход Гротендика и по духу сходный с проектом миноров графов Робертсона и Сеймура, заключается в том, что математический развивается как серия небольших шагов, выполняемых по общей траектории, описываемой подходящей «математической машиной». Авторы подхода предпочитают высказывания следующего типа: Каждый связный граф с n вершинами, удовлетворяющий определенному набору свойств, имеет остовное дерево с не менее чем k листьями, и это остовное дерево можно найти за время <math>O(f(k) + n^c) \;</math>, где c – константа (независимая от k), а f - произвольная функция.
Параметризованная сложность недетерминированного полного алгоритма ОДМЛ с полиномиальным временем выполнения широко изучалась [2, 3, 9, 11] с использованием кернелизации, ветвления и других техник с фиксированными параметрами (fixed-parameter tractable, FPT). Авторы работы [8] первыми предложили метод на базе экстремальной структуры для решения сложных вычислительных задач. Этот метод, выполненный в духе Гротендика и следующий в русле проекта миноров графов Робертсона и Сеймура, заключается в том, что математический проект развивается как серия небольших шагов, выполняемых по общей траектории, описываемой подходящей «математической машиной». Авторы подхода предпочитают высказывания следующего типа: каждый связный граф с n вершинами, удовлетворяющий определенному набору свойств, имеет остовное дерево с не менее чем k листьями, и это остовное дерево можно найти за время <math>O(f(k) + n^c) \;</math>, где c – константа (независимая от k), а f - произвольная функция.




4551

правка

Навигация