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:

Title: Evaluating a weighted graph polynomial for graphs of bounded tree-width
Authors: Noble, S D
Keywords: U polynomial
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$.
ISSN: 1077-8926
Appears in Collections:Mathematics
School of Information Systems, Computing and 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.


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