A Parametrized Algorithm for Matroid Branch-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	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:	Institut Teoretické Informatiky