CAGIRICI, Onur, Petr HLINĚNÝ, Filip POKRÝVKA a Abhisekh SANKARAN. Clique-Width of Point Configurations. Journal of Combinatorial Theory, Ser B. Amsterdam: Elsevier B.V., 2023, roč. 158, č. 1, s. 43-73. ISSN 0095-8956. Dostupné z: https://dx.doi.org/10.1016/j.jctb.2021.09.001. |
Další formáty:
BibTeX
LaTeX
RIS
@article{1799076, author = {Cagirici, Onur and Hliněný, Petr and Pokrývka, Filip and Sankaran, Abhisekh}, article_location = {Amsterdam}, article_number = {1}, doi = {http://dx.doi.org/10.1016/j.jctb.2021.09.001}, keywords = {point configuration; order type; fixed-parameter tractability; relational structure; clique-width}, language = {eng}, issn = {0095-8956}, journal = {Journal of Combinatorial Theory, Ser B}, title = {Clique-Width of Point Configurations}, url = {http://dx.doi.org/10.1016/j.jctb.2021.09.001}, volume = {158}, year = {2023} }
TY - JOUR ID - 1799076 AU - Cagirici, Onur - Hliněný, Petr - Pokrývka, Filip - Sankaran, Abhisekh PY - 2023 TI - Clique-Width of Point Configurations JF - Journal of Combinatorial Theory, Ser B VL - 158 IS - 1 SP - 43-73 EP - 43-73 PB - Elsevier B.V. SN - 00958956 KW - point configuration KW - order type KW - fixed-parameter tractability KW - relational structure KW - clique-width UR - http://dx.doi.org/10.1016/j.jctb.2021.09.001 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 show that it is aligned with the general concept of clique-width of relational structures by Blumensath and Courcelle (2006). We also relate the new notion to 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. \textit{Journal of Combinatorial Theory, Ser B}. Amsterdam: Elsevier B.V., 2023, roč.~158, č.~1, s.~43-73. ISSN~0095-8956. Dostupné z: https://dx.doi.org/10.1016/j.jctb.2021.09.001.
|