Talks and Poster Presentations (with Proceedings-Entry):
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),
- 2013-07-12; in: "Automata, Languages, and Programming - 40th International Colloquium",
Springer / LNCS,
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.