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í
GRAPHS 2009, 2009
Další údaje
Jazyk
angličtina
Typ výsledku
Konferenční abstrakt
Obor
10101 Pure mathematics
Stát vydavatele
Slovensko
Utajení
není předmětem státního či obchodního tajemství
Odkazy
Označené pro přenos do RIV
Ne
Organizační jednotka
Fakulta informatiky
ISBN
978-80-227-3084-6
UT WoS
Klíčová slova česky
parsovací stromy; rank-width; parametrizované algoritmy
Klíčová slova anglicky
parse trees; rank-width; parameterized algorithms
Příznaky
Mezinárodní význam
Změněno: 20. 9. 2009 16:47, RNDr. Robert Ganian, 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
| GC201/09/J021, projekt VaV |
|