Computing the Tutte Polynomial with Restricted “Width”

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

HLINĚNÝ Petr GIMENEZ Omer NOY Marc

Year of publication 2005
MU Faculty or unit

Faculty of Informatics

Citation
Description We discuss some cases when restricting a structural "width" parameter of a graph or a matroid helps to compute the Tutte polynomial faster. Namely, results of Andrzejak and Noble show how to compute the Tutte polynomial efficiently on graphs of bounded tree-width. We show that an efficient computation of the polynomial is possible also in the case of represented matroids of bounded branch-width. As a recent result, we show a subexponential algorithm for computing the Tutte polynomial on graphs of bounded clique-width.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.