Computing the Tutte Polynomial with Restricted “Width”

Varování

Publikace nespadá pod Ekonomicko-správní fakultu, 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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.