Brunel University Research Archive(BURA) preserves and enables easy and open access to all
types of digital content. It showcases Brunel's research outputs.
Research contained within BURA is open access, although some publications may be subject
to publisher imposed embargoes. All awarded PhD theses are also archived on BURA.
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: | Dept of Mathematics Research Papers Mathematical Sciences |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Evaluating a Weighted Graph Polynomial For Graphs of Bounded Tree-Width.pdf | 146.88 kB | Adobe PDF | View/Open |
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.