2009
Better Polynomial Algorithms on Graphs of Bounded Rank-width.
GANIAN, Robert a Petr HLINĚNÝZákladní údaje
Originální název
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 a Petr HLINĚNÝ ORCID
Vydání
IWOCA 2009, 2009
Další údaje
Jazyk
angličtina
Typ výsledku
Konferenční abstrakt
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Česká republika
Utajení
není předmětem státního či obchodního tajemství
Odkazy
Organizační jednotka
Fakulta informatiky
Klíčová slova anglicky
rank-width; parameterized algorithms; graphs
Příznaky
Mezinárodní význam
Změněno: 24. 9. 2013 09:54, prof. RNDr. Petr Hliněný, Ph.D.
V originále
Although there exist many polynomial algorithms for NP-hard problems running on a bounded clique-width expression of the input graph, there exists only little comparable work on such algorithms for rank-width. We believe that one reason for this is the somewhat obscure and hard-to-grasp nature of rank-decompositions. Nevertheless, strong arguments for using the rank-width parameter have been given by recent formalisms independently developed by Courcelle and Kante, by the authors, and by Bui-Xuan et al. This article focuses on designing formally clean and understandable "pseudopolynomial" (XP) algorithms solving "hard" problems (non-FPT) on graphs of bounded rank-width. Those include computing the chromatic number and polynomial or testing the Hamiltonicity of a graph and are extendable to many other problems.
Česky
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.
Návaznosti
| GA201/08/0308, projekt VaV |
| ||
| GC201/09/J021, projekt VaV |
|