Brunel University Research Archive (BURA) >
Schools >
School of Information Systems, Computing and Mathematics >
School of Information Systems, Computing and Mathematics Research Papers >

Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/3374

Title: Evaluating a weighted graph polynomial for graphs of bounded tree-width
Authors: Noble, S D
Keywords: U polynomial
tree-width
polynomial time algorithm
Publication Date: 2009
Publisher: Electronic Journal of Combinatorics
Citation: Electronic Journal of Combinatorics. 16(1) R64, May 2009
Abstract: We show that for any $k$ there is a polynomial time algorithm to evaluate the weighted graph polynomial $U$ of any graph with tree-width at most $k$ at any point. For a graph with $n$ vertices, the algorithm requires $O(a_k n^{2k+3})$ arithmetical operations, where $a_k$ depends only on $k$.
URI: http://bura.brunel.ac.uk/handle/2438/3374
ISSN: 1077-8926
Appears in Collections:School of Information Systems, Computing and Mathematics Research Papers
Mathematical Science

Files in This Item:

File Description SizeFormat
Evaluating a Weighted Graph Polynomial For Graphs of Bounded Tree-Width.pdf146.88 kBAdobe PDFView/Open

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