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

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Název česky	Výpočet Tuttova polynomu na grafech omezené clique-width
Autoři	GIMENEZ Omer HLINĚNÝ Petr NOY Marc
Rok publikování	2005
Druh	Článek ve sborníku
Konference	WG 2005
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
www	doi conference
Obor	Informatika
Klíčová slova	Tutte polynomial; cographs; clique-width; subexponential algorithm; U polynomial
Popis	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.
Související projekty:	Institut Teoretické Informatiky