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;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$.
ISSN: 1077-8926
Appears in Collections:Dept of Mathematics Research Papers
Mathematical Sciences

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.