Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{855539, author = {Ganian, Robert and Hliněný, Petr}, address = {Berlin}, booktitle = {IWOCA 2009: International Workshop On Combinatorial Algorithms, Lecture Notes in Computer Science 5874}, doi = {http://dx.doi.org/10.1007/978-3-642-10217-2}, edition = {5874}, keywords = {rank-width; parameterized algorithms; graphs}, howpublished = {tištěná verze "print"}, language = {eng}, location = {Berlin}, isbn = {978-3-642-10216-5}, pages = {266-277}, publisher = {Springer}, title = {Better Polynomial Algorithms on Graphs of Bounded Rank-width.}, url = {http://dx.doi.org/10.1007/978-3-642-10217-2}, year = {2009} }
TY - JOUR ID - 855539 AU - Ganian, Robert - Hliněný, Petr PY - 2009 TI - Better Polynomial Algorithms on Graphs of Bounded Rank-width. PB - Springer CY - Berlin SN - 9783642102165 KW - rank-width KW - parameterized algorithms KW - graphs UR - http://dx.doi.org/10.1007/978-3-642-10217-2 N2 - 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. ER -
GANIAN, Robert a Petr HLINĚNÝ. Better Polynomial Algorithms on Graphs of Bounded Rank-width. In \textit{IWOCA 2009: International Workshop On Combinatorial Algorithms, Lecture Notes in Computer Science 5874}. 5874. vyd. Berlin: Springer, 2009, s.~266-277. ISBN~978-3-642-10216-5. Dostupné z: https://dx.doi.org/10.1007/978-3-642-10217-2.
|