|
|||||
|
|
ContributionsAn algorithm for the Tutte polynomials of graphs of bounded treewidth |
|
| Authors: | Artur Andrzejak |
| Institution: | ETH Zürich, Departement Informatik, ETH Zentrum, IFW, 8092, Zürich, Switzerland |
| Abstract: | Let k be a fixed, positive integer. We give an algorithm which computes the Tutte polynomial of any graph G of treewidth at most k in time O(n2+7 log2 c), where c is twice the number of partitions of a set with 3k + 3 elements and n the number of vertices of G. |
| Keywords: | Tutte polynomial Computational complexity Bounded treewidth |
| 本文献已被 ScienceDirect 等数据库收录！ | |