Publications in Scientific Journals:
R. Ganian, P. Hlinený, D. Král, J. Obdrzalek, J. Schwartz, J. Teska:
"FO Model Checking of Interval Graphs";
Logical Methods in Computer Science,
11
(2015),
4;
20 pages.
English abstract:
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 solved
in time O(n log n) for n-vertex interval graphs with representations containing only intervals
with lengths from a prescribed nite 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 + ").
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.2168/LMCS-11(4:11)2015
Electronic version of the publication:
http://publik.tuwien.ac.at/files/PubDat_247979.pdf
Created from the Publication Database of the Vienna University of Technology.