Please use this identifier to cite or link to this item:
http://bura.brunel.ac.uk/handle/2438/3374
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Noble, S D | - |
dc.coverage.spatial | 14 | en |
dc.date.accessioned | 2009-06-05T08:14:16Z | - |
dc.date.available | 2009-06-05T08:14:16Z | - |
dc.date.issued | 2009 | - |
dc.identifier.citation | Electronic Journal of Combinatorics. 16(1) R64, May 2009 | en |
dc.identifier.issn | 1077-8926 | - |
dc.identifier.uri | http://bura.brunel.ac.uk/handle/2438/3374 | - |
dc.description.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$. | en |
dc.format.extent | 159420 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.language.iso | en | - |
dc.publisher | Electronic Journal of Combinatorics | en |
dc.subject | U polynomial | en |
dc.subject | tree-width | en |
dc.subject | polynomial time algorithm | en |
dc.title | Evaluating a weighted graph polynomial for graphs of bounded tree-width | en |
dc.type | Research Paper | en |
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.