Informace o publikaci
The Tutte Polynomial for Matroids of Bounded Branch-Width
| Název česky | Tutte polynom na matroidech omezené branch-width |
|---|---|
| Autoři | |
| Rok publikování | 2006 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Combin. Prob. Computing |
| Fakulta / Pracoviště MU | |
| 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: |