Computing the Tutte Polynomial on Graphs of Bounded Clique-Width

Warning

This publication doesn't include Faculty of Education. 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:	Institute for Theoretical Computer Science Highly Parallel and Distributed Computing Systems