Brunel University Research Archive(BURA) preserves and enables easy and open access to all
types of digital content. It showcases Brunel's research outputs.
Research contained within BURA is open access, although some publications may be subject
to publisher imposed embargoes. All awarded PhD theses are also archived on BURA.
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.