algorithm - 图::删除收缩复杂性？

Question

我正在将经典的删除收缩算法应用于“n”个顶点和“m”条边的图 G。

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

在维基百科中， http://en.wikipedia.org/wiki/Chromatic_polynomial#Deletion.E2.80.93contraction

他们说复杂度是:O(1.6180^(n+m))。Mi 的主要问题是为什么他们在复杂性中包含了顶点数？？何时清楚递归仅取决于边数。

与删除收缩最接近的引用文献是斐波那契数列，其计算复杂性在 Herbert S. Wilf 的算法和复杂性一书中进行了演示 http://www.math.upenn.edu/~wilf/AlgComp3.html第 18-19 页。

欢迎所有帮助。

Answer 1

查看 the pdf version 的第 46 页.删除和收缩各减少边数1，所以边的递归只说明Z(G)是O(2^m)，比O(Fib(n + m) ) 除了最稀疏的图之外的所有图。考虑顶点和边的改进是，当形成自环时，我们立即知道色多项式为零。