Další formáty:
BibTeX
LaTeX
RIS
@misc{759261,
author = {Hliněný, Petr and Gimenez, Omer and Noy, Marc},
booktitle = {2nd Workshop on Tutte Polynomials and Applications, CRM, UAB Bellaterra},
language = {eng},
title = {Computing the Tutte Polynomial with Restricted “Width”},
year = {2005}
}
TY - SLIDE
ID - 759261
AU - Hliněný, Petr - Gimenez, Omer - Noy, Marc
PY - 2005
TI - Computing the Tutte Polynomial with Restricted “Width”
N2 - We discuss some cases when restricting a structural "width" parameter of a graph or a matroid helps to compute the Tutte polynomial faster. Namely, results of Andrzejak and Noble show how to compute the Tutte polynomial efficiently on graphs of bounded tree-width. We show that an efficient computation of the polynomial is possible also in the case of represented matroids of bounded branch-width. As a recent result, we show a subexponential algorithm for computing the Tutte polynomial on graphs of bounded clique-width.
ER -
HLINĚNÝ, Petr, Omer GIMENEZ a Marc NOY. Computing the Tutte Polynomial with Restricted “Width”. In \textit{2nd Workshop on Tutte Polynomials and Applications, CRM, UAB Bellaterra}. 2005.
|
