Power Projection of Set Power Series
Introduction 이 글에서는 power projection of set power series를 $O(N^2 2^N+M)$에 계산하는 알고리즘에 대해 알아볼 것이다. 이를 이용해 정점이 $N$개인 그래프의 chromatic polynomial을 $O(N^2 2^N)$에 계산하는 알고리즘도 함께 다룬다. 이 글에서는 Operations on Set Power Series의 내용을 모두 이해했다고 가정하고 설명한다. Power Projection of Set Power Series Set $G = { g_0, g_1, \cdots, g_{N-1} }$과 commutative ring $R$에 대해 정의된 set power series $\mathcal S_G(R)$에 대해 생각하자. 주어진 $a,w \in \mathcal S_G(R)$와 $M \in...