J 2023

Clique-Width of Point Configurations

CAGIRICI, Onur, Petr HLINĚNÝ, Filip POKRÝVKA a Abhisekh SANKARAN

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

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í

Odkazy

Impakt faktor

Impact factor: 1.400 v roce 2022

Kód RIV

RIV/00216224:14330/23:00129924

Organizační jednotka

Fakulta informatiky

DOI

UT WoS

000901805500003

Klíčová slova anglicky

point configuration; order type; fixed-parameter tractability; relational structure; clique-width

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 7. 4. 2024 22:27, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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 VaV
Ná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 MU
Ná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 MU
Ná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.