J 2006

Computing the Tutte Polynomial on Graphs of Bounded Clique-Width

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

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)

Vydání

SIAM Journal on Discrete Mathematics, Philadelphia, SIAM, 2006, 0895-4801

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

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

Odkazy

Impakt faktor

Impact factor: 0.518

Kód RIV

RIV/00216224:14330/06:00015726

Organizační jednotka

Fakulta informatiky

UT WoS

000243967800008

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: 8. 1. 2009 10:08, 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, and extend it 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 a rozšířime jej 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ů
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
1M0545, projekt VaV
Název: Institut Teoretické Informatiky
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky