Подсчитайте количество связующих деревьев быстро

$t(G)$$G$$n$$t(G)$$O(n^3)$QGJ$\frac{1}{n^2} \det(J + Q)$$Q$$G$$J$$1$

Интересно, есть ли способ вычислить $t(G)$ быстрее. (Да, есть более быстрые, чем $O(n^3)$ алгоритмы для вычисления определителя, но меня интересует какой-то новый подход.)

Он также заинтересован в рассмотрении специальных семейств графов (может быть, планарных).

Например, для циркулянтных графов $t(G)$ может быть вычислено в $O(n \lg n)$ арифметических операциях через тождество $t(G) = \frac{1}{n} \lambda_1 \dotsm \lambda_{n-1}$ , где $\lambda_i$ - ненулевые собственные значения матрицы Лапласа группы $G$ , которые можно быстро вычислить для циркулянтных графов. (Представьте первую строку в виде полинома, а затем вычислите ее по $n$ корням единицы - этот шаг использует дискретное преобразование Фурье и может быть выполнен за $O(n \lg n)$ арифметических операций.)

Большое спасибо!

Оно известно , что для ограниченной древесной ширины, Татта полинома может быть оценены в любом с помощью арифметических операции. Если связно, то .$G$$T(G;x,y)$$(x,y)$$O(n)$$G$$t(G)=T(G;1,1)$