J 2019

FO model checking on geometric graphs

HLINĚNÝ, Petr, Filip POKRÝVKA a Bodhayan ROY

Základní údaje

Originální název

FO model checking on geometric graphs

Autoři

HLINĚNÝ, Petr (203 Česká republika, garant, domácí), Filip POKRÝVKA (703 Slovensko, domácí) a Bodhayan ROY (356 Indie, domácí)

Vydání

Computational geometry, Amsterdam, ELSEVIER SCIENCE BV, 2019, 0925-7721

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

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

Odkazy

Impakt faktor

Impact factor: 0.476

Kód RIV

RIV/00216224:14330/19:00107234

Organizační jednotka

Fakulta informatiky

DOI

UT WoS

000452943900001

Klíčová slova anglicky

first-order logic; model checking; fixed-parameter tractability; intersec- tion graphs; visibility graphs

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 14. 4. 2021 21:35, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

V originále

Over the past two decades the main focus of research into first-order (FO) model checking algorithms has been on sparse relational structures – culminating in the FPT algorithm by Grohe, Kreutzer and Siebertz for FO model checking of nowhere dense classes of graphs. On contrary to that, except the case of locally bounded clique-width only little is currently known about FO model checking of dense classes of graphs or other structures. We study the FO model checking problem for dense graph classes definable by geometric means (intersection and visibility graphs). We obtain new nontrivial FPT results, e.g., for restricted subclasses of circular-arc, circle, box, disk, and polygon-visibility graphs. These results use the FPT algorithm by Gajarský et al. for FO model checking of posets of bounded width. We also complement the tractability results by related hardness reductions.

Návaznosti

GA17-00837S, projekt VaV
Název: Strukturální vlastnosti, parametrizovaná řešitelnost a těžkost v kombinatorických problémech
Investor: Grantová agentura ČR, Structural properties, parameterized tractability and hardness in combinatorial problems
MUNI/A/1018/2018, interní kód MU
Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace VIII.
Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace VIII., DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
MUNI/A/1040/2018, interní kód MU
Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 19 (Akronym: SKOMU)
Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 19, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty