Clique-Width of Point Configurations

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Clique-Width of Point Configurations

Popis výsledku v původním jazyce

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ázev v anglickém jazyce

Clique-Width of Point Configurations

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA20-04567S" target="_blank" >GA20-04567S: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Journal of Combinatorial Theory, Ser B

ISSN

0095-8956

e-ISSN

—

Svazek periodika

158

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

31

Strana od-do

43-73

Kód UT WoS článku

000901805500003

EID výsledku v databázi Scopus

2-s2.0-85115385971