R. Ganian,P. Hlinený, D. Král, J. Obdrálek, J. Schwartz, J. Teska:

"FO Model Checking of Interval Graphs";

Talk: International Colloquium on Automata, Languages and Programming (ICALP), Riga, Latvia; 2013-07-08 - 2013-07-12; in: "Automata, Languages, and Programming - 40th International Colloquium", Springer / LNCS, 7966 (2013), ISBN: 978-3-642-39211-5; 250 - 262.

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

FO model checking, parameterized complexity, interval graph, clique-width

Project Head Stefan Szeider:

The Parameterized Complexity of Reasoning Problems

Created from the Publication Database of the Vienna University of Technology.