The complexity of computing the tutte polynomial on transversal matroids |
| |
| Authors: | Charles J. Colbourn J. Scott Provan Dirk Vertigan |
| |
| Affiliation: | (1) Department of Combinatorics and Optimization, University of Waterloo, N2L 3G1 Waterloo, Ontario, Canada;(2) Department of Operations Research, University of North Carolina, 27599-3180 Chapel Hill, North Carolina;(3) Department of Mathematics, Louisiana State University, 70803-4918 Baton Rouge, Louisiana |
| |
| Abstract: | 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. |
| |
| Keywords: | 05 D 15 68 Q 25 68 R 05 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
