Computing the Tutte Polynomial on Graphs of Bounded Clique-Width

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í 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:

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