グラフ::削除の収縮の複雑さ？

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の主な質問は、それらが複雑さの頂点の数を含む理由ですか？再帰がエッジの数にのみ依存することが明らかなとき。

削除収縮に最も近い参照

は、その計算の複雑さは、ハーバート・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））最も希薄なグラフ。エッジと同様に頂点を考慮することの改善は、自己ループが形成されるとき、我々は直ちに色多項式がゼロであることを知る。