Finding branch-decomposition and rank-decomposition

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 branch- a rank-dekompozic
Autoři	HLINĚNÝ Petr OUM Sang-il
Rok publikování	2008
Druh	Článek v odborném periodiku
Časopis / Zdroj	SIAM Journal on Computing
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
www	doi
Obor	Informatika
Klíčová slova	graph; matroid; rank-width; clique-width; branch-width; fixed parameter tractable algorithm
Popis	Přinášíme nový algoritmus, který počítá optimální rank-dekompozici grafu, optimální branch-dekompozici matroidu nad konečným tělesem, v FPT čase n^3.
Související projekty:	Vysoce paralelní a distribuované výpočetní systémy Využití strukturálních a šířkových parametrů v kombinatorice a algoritmické složitosti