График :: Сложность сокращения удаления?

Question

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

Z (G) = Z (G-е) + Z (G/E)

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

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

Ближайшим ссылка на удаление-сжатия является последовательность Фибоначчи, что его вычисления сложность алгоритмов демонстрируется в Herbert S. Уилф и сложность Книга http://www.math.upenn.edu/~wilf/AlgComp3.html страницы 18-19.

Вся помощь приветствуется.

Answer 1

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