Better Polynomial Algorithms on Graphs of Bounded Rank-width.

• Název česky: Lepší polynomiální algoritmy na grafech omezené rank-width
• Autoři: GANIAN Robert; HLINĚNÝ Petr
• Rok publikování: 2009
• Druh: Konferenční abstrakty
• Fakulta / Pracoviště MU: Fakulta informatiky
• Citace: GANIAN, Robert a Petr HLINĚNÝ. Better Polynomial Algorithms on Graphs of Bounded Rank-width. In IWOCA 2009. 2009.
• 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

• Využití strukturálních a šířkových parametrů v kombinatorice a algoritmické složitosti
• Strukturální teorie grafů a parametrizovaná složitost