The complexity of computing the Tutte polynomial on transversal matroids

DOI10.1007/BF01294456zbMath0821.05011OpenAlexW2085669706MaRDI QIDQ1842565

Dirk Vertigan, Charles J. Colbourn, J. Scott Provan

Publication date: 4 May 1995

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01294456

zbMATH Keywords

complexity of computingTutte polynomialtransversal matroids

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Combinatorial aspects of matroids and geometric lattices (05B35) Transversal (matching) theory (05D15)

Related Items (8)

Unnamed Item ⋮ Diverse collections in matroids and graphs ⋮ Lattice path matroids: Enumerative aspects and Tutte polynomials ⋮ The computational complexity of random serial dictatorship ⋮ Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value ⋮ Series-parallel posets and the Tutte polynomial ⋮ Pfaffian pairs and parities: counting on linear matroid intersection and parity problems ⋮ Pfaffian Pairs and Parities: Counting on Linear Matroid Intersection and Parity Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Reliable assignments of processors to tasks and factoring on matroids
• Probabilistic single processor scheduling
• Bicycle dimension and special points of the Tutte polynomial
• The Complexity of Enumeration and Reliability Problems
• On the computational complexity of the Jones and Tutte polynomials
• Bounds on the Reliability Polynomial for Shellable Independence Systems
• The Computational Complexity of Tutte Invariants for Planar Graphs
• Exchange systems, matchings, and transversals

This page was built for publication: The complexity of computing the Tutte polynomial on transversal matroids