Computing the Tutte Polynomial with Restricted “Width”

HLINĚNÝ, Petr; Omer GIMENEZ a Marc NOY. Computing the Tutte Polynomial with Restricted “Width”. In 2nd Workshop on Tutte Polynomials and Applications, CRM, UAB Bellaterra. 2005.

Základní údaje

Originální název

Computing the Tutte Polynomial with Restricted “Width”

Název česky

Výpočet Tuttova polynomu s omezenou "šířkou"

Autoři

HLINĚNÝ, Petr ORCID; Omer GIMENEZ a Marc NOY

Vydání

2nd Workshop on Tutte Polynomials and Applications, CRM, UAB Bellaterra, 2005

---

Další údaje

Jazyk

angličtina

Typ výsledku

Vyžádané přednášky

Obor

10101 Pure mathematics

Utajení

není předmětem státního či obchodního tajemství

Označené pro přenos do RIV

Ne

Organizační jednotka

Fakulta informatiky

Příznaky

Mezinárodní význam

---

Anotace

V originále

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.

---

Návaznosti

GA201/05/0050, projekt VaV	Název: Strukturální vlastnosti a algoritmická složitost diskrétních problémů
MSM0021622419, záměr	Název: Vysoce paralelní a distribuované výpočetní systémy Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy