я получил это уравнение Т (к, п) = 6T (к-1, п-1) к размеру независимого множества п NBR узлов в G. G (V , E)рекуррентного соотношения (параметрироваться анализ)
T (k, n) = 6T (k-1, n-1) = 6 * 6T (k-2, n-2) = ... = 6^k * T (0, n-1) Я застрял здесь.
Алгоритм
Рассмотрим вершину ст. К аргументу preceing вопрос мы предполагаем, что v имеет степень не более 5. Пусть v_1 = V, и пусть v_2, ..., v_6 обозначают соседей V в. Мы напишем простой алгоритм разветвления следующим образом. Есть 6 случаев. В случае i будем считать, что v_i принадлежит к независимому множеству. В этом случае мы удаляем v_i и все его соседи и рекурсивно выполняем поиск по размеру (k-1) несвязанного набора. (Нет причин считать случай, что ни одна из 6 вершин не принадлежит независимому множеству, так как мы всегда можем добавить v_1 к такому решению. Обратите внимание, что несколько соседей v_1 могут принадлежать независимому набору.)
Они сказали, что у него есть sol 6^k * Poly (n)
Вы никогда не говорили, что измеряет T, что всегда важно. Но если мы предположим, что вы используете ОЗУ или аналогичную модель, то все готово. T (0, n-1) = r, где r - постоянное количество вычислений, необходимое для проверки, что k = 0. I.e. требуется постоянное время, чтобы найти, что нет необходимости делать больше вычислений. – Gene
@Gene Но тогда sol должен быть только 6^k вправо? , так как T (0, n-k) принимает постоянное время. Но как получилось, что это было poly (n) – user3105383
Как я уже сказал, вы никогда не говорили, что вы рассчитываете с T. Вероятно, они имеют T (k, n) = w + 6 T (k-1, n-1), где w - постоянный объем работы. Во всяком случае, константа _is_ Poly (n)! – Gene