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. s.~54-66. ISBN~978-3-030-60439-4. doi:10.1007/978-3-030-60440-0\_{}5. 2020.
|
