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
Issue 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:Mathematical Science
Dept of Mathematics Research Papers

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.