Computing the Tutte Polynomial with Restricted “Width”

Varování

Publikace nespadá pod Fakultu sociálních studií, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Název česky	Výpočet Tuttova polynomu s omezenou "šířkou"
Autoři	HLINĚNÝ Petr GIMENEZ Omer NOY Marc
Rok publikování	2005
Druh	Vyžádané přednášky
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
Popis	We discuss some cases when restricting a structural "width" parameter of a graph or a matroid helps to compute the Tutte polynomial faster. Namely, results of Andrzejak and Noble show how to compute the Tutte polynomial efficiently on graphs of bounded tree-width. We show that an efficient computation of the polynomial is possible also in the case of represented matroids of bounded branch-width. As a recent result, we show a subexponential algorithm for computing the Tutte polynomial on graphs of bounded clique-width.
Související projekty:	Vysoce paralelní a distribuované výpočetní systémy