D 2020

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í

Cham, Graph-Theoretic Concepts in Computer Science, WG 2020, od s. 54-66, 13 s. 2020

Nakladatel

Springer, Lecture Notes in Computer Science

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Odkazy

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/20:00114292

Organizační jednotka

Fakulta informatiky

ISBN

978-3-030-60439-4

ISSN

DOI

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: 29. 4. 2021 12:20, 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 relate it to the 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/1050/2019, interní kód MU
Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace IX (Akronym: SV-FI MAV IX)
Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace IX, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
MUNI/A/1076/2019, interní kód MU
Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 20 (Akronym: SKOMU)
Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 20, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty