Computing the Tutte Polynomial on Graphs of Bounded Clique-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

GIMENEZ Omer HLINĚNÝ Petr NOY Marc

Year of publication 2006
Type Article in Periodical
Magazine / Source SIAM Journal on Discrete Mathematics
MU Faculty or unit

Faculty of Informatics

Citation
Web doi
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, and extend it 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.