Name
Abstract | ||
|---|---|---|
It is known that evaluating the Tutte polynomial, T(G; x, y), of a graph, G, is #P-hard at all but eight specific points and one specific curve of the (x, y)-plane. In contrast we show that if k is a fixed constant then for graphs of tree-width at most k there is an algorithm that will evaluate the polynomial at any point using only a linear number of multiplications and additions. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1017/S0963548398003551 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
specific point,tutte polynomial,specific curve,bounded tree-width,linear number,computational complexity | Alternating polynomial,Tutte 12-cage,Discrete mathematics,Stable polynomial,Combinatorics,Tutte polynomial,Tutte theorem,Nowhere-zero flow,Chromatic polynomial,Mathematics,Tutte matrix | Journal |
Volume | Issue | ISSN |
7 | 3 | 0963-5483 |
Citations | PageRank | References |
38 | 1.88 | 6 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| S. D. Noble | 1 | 83 | 9.56 |