Article contents
The Tutte Polynomial for Matroids of Bounded Branch-Width
Published online by Cambridge University Press: 07 April 2006
Abstract
It is a classical result of Jaeger, Vertigan and Welsh that evaluating the Tutte polynomial of a graph is #P-hard in all but a few special points. On the other hand, several papers in the past few years have shown that the Tutte polynomial of a graph can be efficiently computed for graphs of bounded tree-width. In this paper we present a recursive formula computing the Tutte polynomial of a matroid $M$ represented over a finite field (which includes all graphic matroids), using a so called parse tree of a branch-decomposition of $M$. This formula provides an algorithm computing the Tutte polynomial for a representable matroid of bounded branch-width in polynomial time with a fixed exponent.
- Type
- Paper
- Information
- Copyright
- 2006 Cambridge University Press
- 11
- Cited by