Loading...
Please wait, while we are loading the content...
Similar Documents
Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
| Content Provider | Scilit |
|---|---|
| Author | Noble, S. D. |
| Copyright Year | 1998 |
| Description | 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. |
| Related Links | http://bura.brunel.ac.uk/bitstream/2438/817/1/tutte.pdf https://www.cambridge.org/core/services/aop-cambridge-core/content/view/3225A0B606C63B7FC3EE1DC0714595A2/S0963548398003551a.pdf/div-class-title-evaluating-the-tutte-polynomial-for-graphs-of-bounded-tree-width-div.pdf |
| Ending Page | 321 |
| Page Count | 15 |
| Starting Page | 307 |
| ISSN | 09635483 |
| e-ISSN | 14692163 |
| DOI | 10.1017/s0963548398003551 |
| Journal | Combinatorics, Probability and Computing |
| Issue Number | 3 |
| Volume Number | 7 |
| Language | English |
| Publisher | Cambridge University Press (CUP) |
| Publisher Date | 1998-09-01 |
| Access Restriction | Open |
| Subject Keyword | Combinatorics, Probability and Computing Tutte Polynomial Fixed Constant Linear Number Bounded Tree Specific Curve |
| Content Type | Text |
| Resource Type | Article |
| Subject | Applied Mathematics Statistics and Probability Theoretical Computer Science Computational Theory and Mathematics |
