Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{1676037, author = {Cagirici, Onur and Hliněný, Petr and Pokrývka, Filip and Sankaran, Abhisekh}, address = {Cham}, booktitle = {Graph-Theoretic Concepts in Computer Science, WG 2020}, doi = {http://dx.doi.org/10.1007/978-3-030-60440-0_5}, keywords = {point configuration; order type; fixed-parameter tractability; relational structure; clique-width}, howpublished = {tištěná verze "print"}, language = {eng}, location = {Cham}, isbn = {978-3-030-60439-4}, pages = {54-66}, publisher = {Springer, Lecture Notes in Computer Science}, title = {Clique-Width of Point Configurations}, url = {https://arxiv.org/abs/2004.02282}, year = {2020} }
TY - JOUR ID - 1676037 AU - Cagirici, Onur - Hliněný, Petr - Pokrývka, Filip - Sankaran, Abhisekh PY - 2020 TI - Clique-Width of Point Configurations PB - Springer, Lecture Notes in Computer Science CY - Cham SN - 9783030604394 KW - point configuration KW - order type KW - fixed-parameter tractability KW - relational structure KW - clique-width UR - https://arxiv.org/abs/2004.02282 N2 - While structural width parameters (of the input) belong to the standard toolbox of graph algorithms, it is not the usual case in computational geometry. As a case study we propose a natural extension of the structural graph parameter of clique-width to geometric point configurations represented by their order type. We study basic properties of this clique-width notion, and relate it to the monadic second-order logic of point configurations. As an application, we provide several linear FPT time algorithms for geometric point problems which are NP-hard in general, in the special case that the input point set is of bounded clique-width and the clique-width expression is also given. ER -
CAGIRICI, Onur, Petr HLINĚNÝ, Filip POKRÝVKA a Abhisekh SANKARAN. Clique-Width of Point Configurations. In \textit{Graph-Theoretic Concepts in Computer Science, WG 2020}. Cham: Springer, Lecture Notes in Computer Science, 2020, s.~54-66. ISBN~978-3-030-60439-4. Dostupné z: https://dx.doi.org/10.1007/978-3-030-60440-0\_{}5.
|