Computing the Tutte Polynomial on Graphs of Bounded Clique-Width (extended abstract)

Warning

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

GIMENEZ Omer HLINĚNÝ Petr NOY Marc

Year of publication 2005
Type Article in Proceedings
Conference WG 2005
MU Faculty or unit

Faculty of Informatics

Citation
Web
Field Informatics
Keywords Tutte polynomial; cographs; clique-width; subexponential algorithm; U polynomial
Description The Tutte polynomial is a notoriously hard graph invariant, and efficient algorithms for it are known only for a few special graph classes, like for those of bounded tree-width. The notion of clique-width extends the definition of cograhs (graphs without induced P4), and it is a more general notion than that of tree-width. We show a subexponential algorithm (running in time expO(n2/3) ) for computing the Tutte polynomial on cographs. The algorithm can be extended to a subexponential algorithm computing the Tutte polynomial on on all graphs of bounded clique-width. In fact, our algorithm computes the more general U-polynomial.
Related projects:

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