Hostname: page-component-7c8c6479df-xxrs7 Total loading time: 0 Render date: 2024-03-28T23:09:05.822Z Has data issue: false hasContentIssue false

Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width

Published online by Cambridge University Press:  01 September 1998

S. D. NOBLE
Affiliation:
Mathematical Institute, 24–29 St. Giles, Oxford OX1 3LB, England (e-mail: noble@maths.ox.ac.uk)

Abstract

It is known that evaluating the Tutte polynomial, T(G; x, y), of a graph, G, is #P-hard at all but eight specific points and one specific curve of the (x, y)-plane. In contrast we show that if k is a fixed constant then for graphs of tree-width at most k there is an algorithm that will evaluate the polynomial at any point using only a linear number of multiplications and additions.

Type
Research Article
Copyright
1998 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)