Computing the Tutte Polynomial on Graphs of Bounded Clique-Width

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í	2006
Druh	Článek v odborném periodiku
Časopis / Zdroj	SIAM Journal on Discrete Mathematics
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
www	doi
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 a rozšířime jej 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 Vysoce paralelní a distribuované výpočetní systémy