Please use this identifier to cite or link to this item:
http://bura.brunel.ac.uk/handle/2438/817
Title: | Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width |
Authors: | Noble, S D |
Keywords: | Tutte polynomial;graphs of bounded treewidth;computational complexity;linear time algorithm |
Issue Date: | 1998 |
Publisher: | Cambridge University Press |
Citation: | Combinatorics, Probability and Computing, (1998) 7, 307-321 |
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. |
URI: | http://bura.brunel.ac.uk/handle/2438/817 |
ISSN: | 09635483 |
Appears in Collections: | Computer Science Mathematical Sciences |
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.