Clique-Width of Point Configurations

Logo poskytovatele

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Autoři

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

Rok publikování 2022
Druh Článek v odborném periodiku
Časopis / Zdroj Journal of Combinatorial Theory, Ser B
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www open access preprint
Doi http://dx.doi.org/10.1016/j.jctb.2021.09.001
Klíčová slova point configuration; order type; fixed-parameter tractability; relational structure; clique-width
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info