FO Model Checking of Interval Graphs

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

FO Model Checking of Interval Graphs

Original language description

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).

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

IN - Informatics

OECD FORD branch

—

Project

<a href="/en/project/GAP202%2F11%2F0196" target="_blank" >GAP202/11/0196: Well-structured combinatorial classes, width parameters, and design of efficient algorithms</a><br>

Continuities

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

Publication year

2013

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

ICALP (2) 2013

ISBN

9783642392115

ISSN

0302-9743

e-ISSN

—

Number of pages

13

Pages from-to

250-262

Publisher name

Springer

Place of publication

Berlin Heidelberg

Event location

Riga, Latvia

Event date

Jan 1, 2013

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—