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., roč. 2023, č. 158, s. 43-73. ISSN 0095-8956. doi:10.1016/j.jctb.2021.09.001. 2023.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název Clique-Width of Point Configurations
Autoři CAGIRICI, Onur (792 Turecko, domácí), Petr HLINĚNÝ (203 Česká republika, garant, domácí), Filip POKRÝVKA (703 Slovensko, domácí) a Abhisekh SANKARAN (356 Indie).
Vydání Journal of Combinatorial Theory, Ser B, Amsterdam, Elsevier B.V. 2023, 0095-8956.
Další údaje
Originální jazyk angličtina
Typ výsledku Článek v odborném periodiku
Obor 10201 Computer sciences, information science, bioinformatics
Stát vydavatele Nizozemské království
Utajení není předmětem státního či obchodního tajemství
WWW open access preprint DOI
Impakt faktor Impact factor: 1.400 v roce 2022
Organizační jednotka Fakulta informatiky
Doi http://dx.doi.org/10.1016/j.jctb.2021.09.001
UT WoS 000901805500003
Klíčová slova anglicky point configuration; order type; fixed-parameter tractability; relational structure; clique-width
Štítky formela-journal
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: prof. RNDr. Petr Hliněný, Ph.D., učo 168881. Změněno: 28. 6. 2023 13:46.
Anotace
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.
Návaznosti
GA20-04567S, projekt VaVNázev: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech
Investor: Grantová agentura ČR, Structure of tractable instances of hard algorithmic problems on graphs
MUNI/A/1081/2022, interní kód MUNázev: Modelování, analýza a verifikace (2023)
Investor: Masarykova univerzita, Modelování, analýza a verifikace (2023)
MUNI/A/1145/2021, interní kód MUNázev: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace XI. (Akronym: SV-FI MAV XI.)
Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace XI.
VytisknoutZobrazeno: 29. 3. 2024 06:04