D 2005

Computing the Tutte Polynomial on Graphs of Bounded Clique-Width (extended abstract)

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

Základní údaje

Originální název

Computing the Tutte Polynomial on Graphs of Bounded Clique-Width (extended abstract)

Název česky

Výpočet Tuttova polynomu na grafech omezené clique-width

Autoři

GIMENEZ, Omer (724 Španělsko), Petr HLINĚNÝ (203 Česká republika, garant) a Marc NOY (724 Španělsko)
D. Kratsch (Ed.).

Vydání

Berlin, WG 2005, od s. 59-68, 10 s. 2005

Nakladatel

Springer Verlag

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

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

Odkazy

Kód RIV

RIV/00216224:14330/05:00012661

Organizační jednotka

Fakulta informatiky

ISBN

978-3-540-31000-6

UT WoS

000234875500006

Klíčová slova anglicky

Tutte polynomial; cographs; clique-width; subexponential algorithm; U polynomial

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 24. 3. 2010 14:11, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

ORIG CZ

V originále

The Tutte polynomial is a notoriously hard graph invariant, and efficient algorithms for it are known only for a few special graph classes, like for those of bounded tree-width. The notion of clique-width extends the definition of cograhs (graphs without induced P4), and it is a more general notion than that of tree-width. We show a subexponential algorithm (running in time expO(n2/3) ) for computing the Tutte polynomial on cographs. The algorithm can be extended to a subexponential algorithm computing the Tutte polynomial on on all graphs of bounded clique-width. In fact, our algorithm computes the more general U-polynomial.

Česky

Tuttův polynom je známý obtížný grafový invariant, pro který jsou známy efektivní algoritmy jen v několika třídách grafů jako ty s omezenou stromovou šířkou. Pojem klikové šířky rozšiřuje kografy a je obecnější než stromová šířka. My ukážeme subexponeciální algoritmus (v čase expO(n2/3) ) počítající Tuttův polynom na kografech. Tento algoritmus je možno rozšířit na subexponenciální algoritmus pro všechny grafy omezené klikové šířky. Náš algoritmus dokonce počítá tzv. U-polynom.

Návaznosti

GA201/05/0050, projekt VaV
Název: Strukturální vlastnosti a algoritmická složitost diskrétních problémů
1M0545, projekt VaV
Název: Institut Teoretické Informatiky
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky