Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
Computing the tutte polynomial on graphs of bounded clique-width
Ist Teil von
SIAM journal on discrete mathematics, 2006-01, Vol.20 (4), p.932-946
Ort / Verlag
Philadelphia, PA: Society for Industrial and Applied Mathematics
Erscheinungsjahr
2006
Link zum Volltext
Quelle
Alma/SFX Local Collection
Beschreibungen/Notizen
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 cographs (graphs without induced $P_4$), and it is a more general notion than that of tree-width. We show a subexponential algorithm (running in time $\exp{O(n^{1-\varepsilon})}\,$) for computing the Tutte polynomial on graphs of bounded clique-width. In fact, our algorithm computes the more general $U$-polynomial.