FO Model Checking of Interval Graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F15%3A00081403" target="_blank" >RIV/00216224:14330/15:00081403 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.2168/LMCS-11(4:11)2015" target="_blank" >http://dx.doi.org/10.2168/LMCS-11(4:11)2015</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.2168/LMCS-11(4:11)2015" target="_blank" >10.2168/LMCS-11(4:11)2015</a>

Jazyk výsledku

angličtina

Název v původním jazyce

FO Model Checking of Interval Graphs

Popis výsledku v původním jazyce

We study the computational complexity of the FO model checking problem on interval graphs, i.e., intersection graphs of intervals on the real line. The main positive result is that FO model checking and successor-invariant FO model checking can be solvedin time O(n log n) for n-vertex interval graphs with representations containing only intervals with lengths from a prescribed finite set. We complement this result by showing that the same is not true if the lengths are restricted to any set that is dense in an open subset, e.g., in the set (1, 1 + ?).

Název v anglickém jazyce

FO Model Checking of Interval Graphs

Popis výsledku anglicky

We study the computational complexity of the FO model checking problem on interval graphs, i.e., intersection graphs of intervals on the real line. The main positive result is that FO model checking and successor-invariant FO model checking can be solvedin time O(n log n) for n-vertex interval graphs with representations containing only intervals with lengths from a prescribed finite set. We complement this result by showing that the same is not true if the lengths are restricted to any set that is dense in an open subset, e.g., in the set (1, 1 + ?).

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA14-03501S" target="_blank" >GA14-03501S: Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky</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í

2015

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

Logical Methods in Computer Science

ISSN

1860-5974

e-ISSN

—

Svazek periodika

11

Číslo periodika v rámci svazku

4:11

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

20

Strana od-do

1-20

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—