The Tutte Polynomial for Matroids of Bounded Branch-Width

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Název česky	Tutte polynom na matroidech omezené branch-width
Autoři	HLINĚNÝ Petr
Rok publikování	2006
Druh	Článek v odborném periodiku
Časopis / Zdroj	Combin. Prob. Computing
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
www	doi http://journals.cambridge.org/action/displayJournal?jid=CPC
Obor	Obecná matematika
Klíčová slova	representable matroid; Tutte polynomial; branch-width;
Popis	Klasický výsledek od Jaeger, Vertigan a Welsh říká, že Tuttův polynom grafu je #P-těžké vypočítat všude mimo několika speciálních bodů. Na druhou stranu několik dřívějších výsledků ukázalo, že Tuttův polynom lze efektivně vypočítat na grafech omezené tree-width. V našem článku ukážeme rekurzivní formuli, která umožňuje vypočítat Tuttův polynom matroidu reprezentovaného nad konečným tělesem za použití parsovacího stromu jeho větvené dekompozice. Tato formule ukazuje, jak efektivně vypočíst Tuttův polynom reprezentovaného matroidu s fixním exponentem.
Související projekty:	Institut Teoretické Informatiky