Evaluating a weighted graph polynomial for graphs of bounded tree-width (Q1028845)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Evaluating a weighted graph polynomial for graphs of bounded tree-width |
scientific article; zbMATH DE number 5576445
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Evaluating a weighted graph polynomial for graphs of bounded tree-width |
scientific article; zbMATH DE number 5576445 |
Statements
Evaluating a weighted graph polynomial for graphs of bounded tree-width (English)
0 references
8 July 2009
0 references
Summary: 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\).
0 references
