FO model checking; parameterized complexity; interval graph; clique-width
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F13%3A43919150" target="_blank" >RIV/49777513:23520/13:43919150 - 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>
Alternative languages
Result language
angličtina
Original language name
FO model checking; parameterized complexity; interval graph; clique-width
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 +?).
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
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)
Others
Publication year
2013
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of 40th International Colloquium on Automata, Languages and Programming (ICALP 2013)
ISBN
978-3-642-39211-5
ISSN
—
e-ISSN
—
Number of pages
13
Pages from-to
250-262
Publisher name
Springer
Place of publication
Heidelberg
Event location
Riga, Litva
Event date
Jul 8, 2013
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—