The Tutte Polynomial for Matroids of Bounded Branch-Width

Varování

Publikace nespadá pod Filozofickou fakultu, 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
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:

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