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%2F13%3A00066379" target="_blank" >RIV/00216224:14330/13:00066379 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-642-39212-2_24" target="_blank" >http://dx.doi.org/10.1007/978-3-642-39212-2_24</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-642-39212-2_24" target="_blank" >10.1007/978-3-642-39212-2_24</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 this problem can be solved in 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 some open subset, e.g., in the set (1, 1+epsilon).

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 this problem can be solved in 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 some open subset, e.g., in the set (1, 1+epsilon).

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GAP202%2F11%2F0196" target="_blank" >GAP202/11/0196: Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2013

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 statě ve sborníku

ICALP (2) 2013

ISBN

9783642392115

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

13

Strana od-do

250-262

Název nakladatele

Springer

Místo vydání

Berlin Heidelberg

Místo konání akce

Riga, Latvia

Datum konání akce

1. 1. 2013

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—