![Důležité termíny](https://cdn.muni.cz/media/3716855/image_2.jpg?mode=crop¢er=0.5,0.5&rnd=133667368190000000&heightratio=0.5&width=278)
Informace o publikaci
Computing the Tutte Polynomial with Restricted “Width”
Název česky | Výpočet Tuttova polynomu s omezenou "šířkou" |
---|---|
Autoři | |
Rok publikování | 2005 |
Druh | Vyžádané přednášky |
Fakulta / Pracoviště MU | |
Citace | |
Popis | 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. |
Související projekty: |