Computing the Tutte Polynomial with Restricted "Width"

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F05%3A00012171" target="_blank" >RIV/61989100:27240/05:00012171 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Computing the Tutte Polynomial with Restricted "Width"

Popis výsledku v původním jazyce

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. (Parts of this talk are based on a joint work with O. Gimenez and M. Noy.)

Název v anglickém jazyce

Computing the Tutte Polynomial with Restricted "Width"

Popis výsledku anglicky

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. (Parts of this talk are based on a joint work with O. Gimenez and M. Noy.)

Druh

A - Audiovizuální tvorba

CEP obor

BD - Teorie informace

OECD FORD obor

—

Projekt

<a href="/cs/project/GA201%2F05%2F0050" target="_blank" >GA201/05/0050: Strukturální vlastnosti a algoritmická složitost diskrétních problémů</a><br>

Návaznosti

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

Rok uplatnění

2005

Kód důvěrnosti údajů

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

ISBN

—

Místo vydání

Barcelona

Název nakladatele resp. objednatele

Centre de Recerca Matematika

Verze

—

Identifikační číslo nosiče

—