A Parametrized Algorithm for Matroid Branch-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 Parametrizovaný algoritmus pro branch-width matroidů
Autoři

HLINĚNÝ Petr

Rok publikování 2005
Druh Článek v odborném periodiku
Časopis / Zdroj SIAM Journal on Computing
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www http://epubs.siam.org/sam-bin/dbq/toc/SICOMP/35/2
Obor Informatika
Klíčová slova representable matroid; parametrized algorithm; branch-width; rank-width
Popis Branch-width je strukturální parametr blízký známé tree-width, avšak mající okamžité zobecnění na matroidy. Zde uvedeme algoritmus, který pro daný matroid M s omezenou branch-width ta reprezentovaný nad konečným tělesem najde dekompozici šířky nejvýše 3t v kubickém čase. Tak dokážeme, že branch-width je uniformně FPT problém. Další aplikace zahrnují rozpoznávání matroidových vlastností v monadické logice druhého řádu pro omezenou branch-width, nebo [Oum] kubický aproximační algoritmus pro grafovou rank-width a clique-width.
Související projekty:

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