D 2018

FO model checking of geometric graphs

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

Základní údaje

Originální název

FO model checking of 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í

LIPIcs 89. Dagstuhl, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), od s. "19:1"-"19:12", 12 s. 2018

Nakladatel

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

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í

elektronická verze "online"

Kód RIV

RIV/00216224:14330/18:00100734

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-051-4

ISSN

DOI

Klíčová slova anglicky

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

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 14. 6. 2022 12:12, RNDr. Pavel Šmerk, 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/0897/2016, interní kód MU
Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace VI.
Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace VI., DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
MUNI/A/0992/2016, interní kód MU
Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Akronym: SKOMU)
Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty