Zeitschriftenartikel:
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 S.
Kurzfassung englisch:
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 + ").
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.2168/LMCS-11(4:11)2015
Elektronische Version der Publikation:
http://publik.tuwien.ac.at/files/PubDat_247979.pdf
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.