FO model checking on geometric graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F19%3A00107234" target="_blank" >RIV/00216224:14330/19:00107234 - isvavai.cz</a>

Výsledek na webu

<a href="https://arxiv.org/abs/1709.03701" target="_blank" >https://arxiv.org/abs/1709.03701</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.comgeo.2018.10.001" target="_blank" >10.1016/j.comgeo.2018.10.001</a>

Jazyk výsledku

angličtina

Název v původním jazyce

FO model checking on geometric graphs

Popis výsledku v původním jazyce

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

FO model checking on geometric graphs

Popis výsledku anglicky

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.

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/GA17-00837S" target="_blank" >GA17-00837S: Strukturální vlastnosti, parametrizovaná řešitelnost a těžkost v kombinatorických problémech</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í

2019

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

Computational geometry

ISSN

0925-7721

e-ISSN

—

Svazek periodika

78

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

19

Strana od-do

1-19

Kód UT WoS článku

000452943900001

EID výsledku v databázi Scopus

2-s2.0-85055655920