Better Polynomial Algorithms on Graphs of Bounded Rank-width.

Varování

Publikace nespadá pod Pedagogickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Název česky	Lepší polynomiální algoritmy na grafech omezené rank-width
Autoři	GANIAN Robert HLINĚNÝ Petr
Rok publikování	2009
Druh	Článek ve sborníku
Konference	IWOCA 2009: International Workshop On Combinatorial Algorithms, Lecture Notes in Computer Science 5874
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
www	DOI
Doi	http://dx.doi.org/10.1007/978-3-642-10217-2
Obor	Informatika
Klíčová slova	rank-width; parameterized algorithms; graphs
Popis	Ačkoliv existuje mnoho polynomiálních algoritmů pro NP-těžké problémy na grafech omezené clique-width, o podobných algoritmech využívajících rank-width je toho známo velmi málo. Článek se zaměřuje na vývoj efektivních a formálně "čistých" algoritmů na grafech omezené rank-width.
Související projekty:	Institut Teoretické Informatiky Vysoce paralelní a distribuované výpočetní systémy Využití strukturálních a šířkových parametrů v kombinatorice a algoritmické složitosti Parameterized Algorithms and Width measures on Graphs Rozsáhlé výpočetní systémy: modely, aplikace a verifikace