Automata Approach to Graphs of Bounded Rank-width

• 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
• 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