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