Clique-Width of Point Configurations
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F23%3A00129924" target="_blank" >RIV/00216224:14330/23:00129924 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1016/j.jctb.2021.09.001" target="_blank" >http://dx.doi.org/10.1016/j.jctb.2021.09.001</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.jctb.2021.09.001" target="_blank" >10.1016/j.jctb.2021.09.001</a>
Alternative languages
Result language
angličtina
Original language name
Clique-Width of Point Configurations
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA20-04567S" target="_blank" >GA20-04567S: Structure of tractable instances of hard algorithmic problems on graphs</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Journal of Combinatorial Theory, Ser B
ISSN
0095-8956
e-ISSN
—
Volume of the periodical
158
Issue of the periodical within the volume
1
Country of publishing house
NL - THE KINGDOM OF THE NETHERLANDS
Number of pages
31
Pages from-to
43-73
UT code for WoS article
000901805500003
EID of the result in the Scopus database
2-s2.0-85115385971