Brunel University Research Archive (BURA) >
Research Areas >
Information Systems and Computing >

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
Publication 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:Mathematics
Information Systems and Computing

Files in This Item:

File Description SizeFormat
tutte.pdf235.24 kBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.

 


Library (c) Brunel University.    Powered By: DSpace
Send us your
Feedback. Last Updated: September 14, 2010.
Managed by:
Hassan Bhuiyan