Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-09T15:13:14.916Z Has data issue: false hasContentIssue false

The Tutte Polynomial for Matroids of Bounded Branch-Width

Published online by Cambridge University Press:  07 April 2006

PETR HLINĚNÝ
Affiliation:
School of Mathematical and Computing Sciences, Victoria University of Wellington, PO Box 600, Wellington, New Zealand (e-mail: petr.hlineny@vsb.cz) Current affiliation and mailing address: Department of Computer Science, FEI VšB – Technical University of Ostrava, 17. listopadu 15, 70833 Ostrava, Czech Republic.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Paper
Copyright
2006 Cambridge University Press