Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
R. Ganian, P. Hlinený, D. Král, J. Obdrálek, J. Schwartz, J. Teska:
"FO Model Checking of Interval Graphs";
Vortrag: International Colloquium on Automata, Languages and Programming (ICALP),
Riga, Latvia;
08.07.2013
- 12.07.2013; in: "Automata, Languages, and Programming - 40th International Colloquium",
Springer / LNCS,
7966
(2013),
ISBN: 978-3-642-39211-5;
S. 250
- 262.
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 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).
Schlagworte:
FO model checking, parameterized complexity, interval graph, clique-width
Zugeordnete Projekte:
Projektleitung Stefan Szeider:
The Parameterized Complexity of Reasoning Problems
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.