Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
复制标题
评估有界树宽度图的 Tutte 多项式
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
S. Noble
中科院分区：
文献类型：
--
作者：
S. Noble
众所周知，要计算一个图形 G 的 Tutte 多项式 T(G; x, y) 除了在 (x, y) 平面上的八个特定点和一条特定曲线外，在其他地方都是 #P 难的。相反，我们证明，如果 k 是一个固定常数，那么对于树宽最多为 k 的图，有一种算法只需线性的乘法和加法就能求得任意点的多项式。
It is known that evaluating the Tutte polynomial, T(G; x, y), of a graph, G, is #P-hard at all but eight specific points and one specific curve of the (x, y)-plane. In contrast we show that if k is a fixed constant then for graphs of tree-width at most k there is an algorithm that will evaluate the polynomial at any point using only a linear number of multiplications and additions.