Automata Approach to Graphs of Bounded Rank-width

Varování

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

Název česky	Automatové zpracování grafů omezené rank-width
Autoři	HLINĚNÝ Petr GANIAN Robert
Rok publikování	2008
Druh	Článek ve sborníku
Konference	International Workshop on Combinatorial Algorithms IWOCA 2008
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
www	conference
Obor	Informatika
Klíčová slova	parameterized algorithm; rank-width; tree automaton; MSO logic
Popis	V příspěvku popisujeme nový nezávislý popis rankové dekompozice grafu pomocí speciálních parsovacích stromů. V tomto popisu následně ukazujeme ekvivalent Myhill-Nerodovy věty a jeho použití v návrhu algoritmů pro grafy omezené rank-width.
Související projekty:	Institut Teoretické Informatiky Využití strukturálních a šířkových parametrů v kombinatorice a algoritmické složitosti