Finding branch-decomposition and rank-decomposition

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