The Tutte Polynomial for Matroids of Bounded Branch-Width

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F06%3A00016574" target="_blank" >RIV/00216224:14330/06:00016574 - isvavai.cz</a>

Alternative codes found

RIV/61989100:27240/06:00013751

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

The Tutte Polynomial for Matroids of Bounded Branch-Width

Original language description

It is a classical result of Jaeger, Vertigan and Welsh that evaluating the Tutte polynomial of a graph is $#P$-hard in all but few special points. On the other hand, several papers in past years have shown that the Tutte polynomial of a graph can be efficiently computed for graphs of bounded tree-width. In this paper we present a recursive formula computing the Tutte polynomial of a matroid $md M$ represented over a finite field (which includes all graphic matroids), using a so called parse tree of abranch-decomposition of $md M$. This formula provides an algorithm computing the Tutte polynomial for a representable matroid of bounded branch-width in polynomial time with a fixed exponent.

Czech name

Tutte polynom na matroidech omezené branch-width

Czech description

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 polynomreprezentovaného matroidu s fixním exponentem.

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2006

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Combin. Prob. Computing

ISSN

0963-5483

e-ISSN

—

Volume of the periodical

15

Issue of the periodical within the volume

3

Country of publishing house

GB - UNITED KINGDOM

Number of pages

13

Pages from-to

397

UT code for WoS article

—

EID of the result in the Scopus database

—