The complexity of computing the tutte polynomial on transversal matroids
The complexity of computing the tutte polynomial on transversal matroids
复制标题
计算横向拟阵上的 tutte 多项式的复杂度
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
D. Vertigan
中科院分区：
文献类型：
--
作者：
C. Colbourn;J. Scott Provan;D. Vertigan
确定了Tutte多项式T(M，x，y)对于横截拟阵M和代数数x Andy的计算复杂性。证明了对于固定的x andy，计算横截拟阵T(M，x，y)的问题是#P-完全的，除非x andy满足(x−1)(y−1)=1，在这种情况下它是多项式时间可计算的.特别地，计算横截拟阵中的基数和计算二部图中各种类型的“可匹配”结点集的问题是#P-完全的。
The complexity of computing the Tutte polynomialT(M,x,y) is determined for transversal matroidM and algebraic numbersx andy. It is shown that for fixedx andy the problem of computingT(M,x,y) forM a transversal matroid is #P-complete unless the numbersx andy satisfy (x−1)(y−1)=1, in which case it is polynomial-time computable. In particular, the problem of counting bases in a transversal matroid, and of counting various types of “matchable” sets of nodes in a bipartite graph, is #P-complete.