Computing the Tutte Polynomial on Graphs of Bounded Clique-Width (extended abstract)
| Authors | |
|---|---|
| Year of publication | 2005 |
| Type | Article in Proceedings |
| Conference | WG 2005 |
| MU Faculty or unit | |
| 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: |