The Computational Complexity of the Tutte Plane: the Bipartite Case
The Computational Complexity of the Tutte Plane: the Bipartite Case
复制标题
DOI：
10.1017/s0963548300000195
复制
发表时间：
1992-06
期刊：
影响因子：
--
通讯作者：
D. Vertigan;D. Welsh
中科院分区：
文献类型：
--
作者：
D. Vertigan;D. Welsh
沿着不同的曲线，在（x, y）平面的不同点，Tutte多项式计算的量范围很广。其中一些可以在多项式时间内计算，例如图的生成树的数量和平面Ising模型的配分函数，其他的则是# P-hard。这里我们给出了在二部情况下哪些点和曲线是容易/困难的一个完整的特征。
Along different curves and at different points of the (x, y)-plane the Tutte polynomial evaluates a wide range of quantities. Some of these, such as the number of spanning trees of a graph and the partition function of the planar Ising model, can be computed in polynomial time, others are # P-hard. Here we give a complete characterisation of which points and curves are easy/hard in the bipartite case.