Další formáty:
BibTeX
LaTeX
RIS
@article{589844,
author = {Hliněný, Petr},
article_location = {UK},
article_number = {3},
keywords = {representable matroid; Tutte polynomial; branch-width;},
language = {eng},
issn = {0963-5483},
journal = {Combin. Prob. Computing},
title = {The Tutte Polynomial for Matroids of Bounded Branch-Width},
url = {http://dx.doi.org/10.1017/S0963548305007297},
volume = {15},
year = {2006}
}
TY - JOUR
ID - 589844
AU - Hliněný, Petr
PY - 2006
TI - The Tutte Polynomial for Matroids of Bounded Branch-Width
JF - Combin. Prob. Computing
VL - 15
IS - 3
SP - 397
EP - 397
PB - Cambridge Univ. Press
SN - 09635483
KW - representable matroid
KW - Tutte polynomial
KW - branch-width;
UR - http://dx.doi.org/10.1017/S0963548305007297
N2 - 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 a branch-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.
ER -
HLINĚNÝ, Petr. The Tutte Polynomial for Matroids of Bounded Branch-Width. \textit{Combin. Prob. Computing}. UK: Cambridge Univ. Press, roč.~15, č.~3, s.~397-409. ISSN~0963-5483. 2006.
|
