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

Varování

Publikace nespadá pod Filozofickou fakultu, 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
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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.