Graph :: Deletion Сокращение Сложность?

Question

Я применяю классический алгоритм сокращения удаления к графу G из "n" вершин и "m" ребер.

Z (G) = Z (Ge) + Z (G / e)

В Википедии http://en.wikipedia.org/wiki/Chromatic_polynomial#Deletion.E2.80.93contraction

Говорят, что сложность равна: O (1.6180 ^ (n + m)).Ми главный вопрос, почему они включили количество вершин в сложность ??когда ясно, что рекурсия зависит только от числа ребер.

Ближайшая ссылка на сокращение-сокращение - это последовательность Фибоначчи, сложность ее вычисления продемонстрирована в книге Герберта С. Уилфа "Алгоритмы и сложность" http://www.math.upenn.edu/~wilf/AlgComp3.html стр. 18-19.

Любая помощь приветствуется.

Answer 1

Посмотрите на странице 46 из в формате PDF .Удаление и сжатие уменьшают количество ребер на 1, поэтому повторение ребер только показывает, что Z (G) равно O (2 ^m ), что хуже, чем O (Fib (n + m))для всех, кроме самых редких графов.Улучшение в рассмотрении как вершин, так и ребер заключается в том, что при формировании самоконтроля мы сразу же узнаем, что хроматический полином равен нулю.